Parallel algorithms for finding Hamilton cycles in random graphs

DOI10.1016/0020-0190(87)90229-8MaRDI QIDQ1108039zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Alan 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 programmingHamilton cycleparallel algorithmrandom graph

Mathematics Subject Classification ID

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

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

Cited in

(4)

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

This page was built for publication: Parallel algorithms for finding Hamilton cycles in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108039)