A simple linear expected time algorithm for finding a Hamilton path
type: Item
instance of: scholarly article
title: A simple linear expected time algorithm for finding a Hamilton path
zbMATH Open document ID: 0681.05051
DOI: 10.1016/0012-365X(89)90100-3
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: Since the problem of finding a Hamiltonian path between two vertices of a graph, or showing that no such path exists, is NP-complete, it is natural to look for algorithms which are fast for most graphs. In [\textit{Y. Gorevich} and \textit{S. Shelah}, Expected computation time for Hamiltonian path problem and clique problem, SIAM J. Comput. 16, 486-502 (1987; Zbl 0654.68083)] an algorithm is presented which runs in expected time cn/p (c is a constant) and requires \(O(n^ 2)\) storage on a random n-vertex graph where edges appear with probability p, provided p is a constant. The paper under review presents a simpler algorithm which requires only on storage and runs in expected time cn/p if \(p\geq 12n^{-1/3}\). The algorithm is easily modified to find (or show the non-existence of) a Hamiltonian cycle with no change in the space or expected time bounds; similar modifications can be made for directed graphs.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4114682
author: Andrew Thomason
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: Fast probabilistic algorithms for Hamiltonian circuits and matchings
cites work: Q3682518
cites work: An algorithm for finding Hamilton paths and cycles in random graphs
cites work: A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
cites work: A note on Hamiltonian circuits
cites work: Paths, Trees, and Flowers
cites work: Expected Computation Time for Hamiltonian Path problem
cites work: A Dynamic Programming Approach to Sequencing Problems
cites work: The NP-completeness column: An ongoing guide
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: How many random edges make a graph Hamiltonian?
cites work: Q3768936
description: scientific article; zbMATH DE number 4114682