Parallel algorithms for finding Hamilton cycles in random graphs

DOI10.1016/0020-0190(87)90229-8zbMath0653.68071OpenAlexW1996876354WikidataQ57401626 ScholiaQ57401626MaRDI QIDQ1108039

Alan M. Frieze

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90229-8

zbMATH Keywords

dynamic programmingparallel algorithmrandom graphHamilton cycle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items

Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs, The Hamilton circuit problem on grids, A fast parallel algorithm for finding Hamiltonian cycles in dense graphs, Parallel graph algorithms that are efficients on average

Cites Work

• A simple linear expected time algorithm for finding a Hamilton path
• Expected Computation Time for Hamiltonian Path problem
• Parallelism in random access machines