Obtaining hamilton cicuits in graphs and digraphs

2002/10/09 by Howard Kleiman, Kleiman, Howard
Mathematics · #05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05

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

PDF file. 110 pages

arxiv created 2002/10/09 · arxiv updated 2009/11/30

Abstract

This paper improves algorithms given in math.CO/0012036. Although the graph (digraph) becomes non-random as the algorithm proceeds, the probability for success stays the same. We also give examples.

Related

• Hamilton Circuits in Graphs and Directed Graphs
• An O(n) time algorithm for finding Hamilton cycles with high probability
• Fast algorithms for solving the Hamilton Cycle problem with high\n probability
• Packing, Counting and Covering Hamilton cycles in random directed graphs
• Finding a Hamilton cycle fast on average using rotations and extensions