On an Algorithm of Frieze

2001/02/20 by Howard Kleiman, Kleiman, Howard
Computer Science · Mathematics · #05C85 #Advanced Combinatorial Mathematics #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Stochastic processes and statistical mechanics #math.CO #msc:05C85

paper · pdf · doi:10.48550/arxiv.math/0102155

This is a very simple version of the original algorithm together with a detailed illustration of it in Example 2.1 . It is the second chapter of a book - "P = NP? Admissible Permutations and the HCP, the AP, and the TSP" - nearly completed. This version contains two figures

openalex publication_date 2001/02/20 · arxiv created 2002/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The algorithm reduces the running time of an algorithm of Frieze from O(n^1.5)) to O(n^(4/3 + o)). It also introduces the concept of admissible permutations that is used in algorithms for obtaining solutions to the AP and the TSP.

Related

• The Floyd-Warshall Algorithm, the AP and the TSP III
• A Deterministic Algorithm for the Frieze–Kannan Regularity Lemma
• The Floyd-WarshallAlgorithm and the Asymmetric TSP
• Solution Bounds for a Hypothetical Polynomial Time Aproximation Algorithm for the TSP
• The Floyd-Warshall Algorithm, the AP and the TSP, Part II