Finding hidden hamiltonian cycles

DOI10.1002/RSA.3240050303MaRDI QIDQ4306372zbMATHOpenAlexDBLPWikidataFDO

Authors Andrei Broder, Eli Shamir, Alan Frieze

Publication date 20 March 1995

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.3240050303

zbMATH Keywords

sparse graphsHamiltonian cyclesrandom graphscoversearch algorithmsedge disjoint paths

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Recommendations

• Finding Hamilton cycles in sparse random graphs
• An algorithm for finding Hamilton paths and cycles in random graphs
• scientific article; zbMATH DE number 3912424
• An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three

Cited in

(14)

• On a simple randomized algorithm for finding a 2-factor in sparse graphs
• Finding Hamilton cycles in sparse random graphs
• Iterative algorithm for discrete structure recovery
• HybridHAM: a novel hybrid heuristic for finding Hamiltonian cycle
• scientific article; zbMATH DE number 4123549 (Why is no real title available?)
• An extension of the multi-path algorithm for finding Hamilton cycles
• The forgetfulness of balls and bins
• scientific article; zbMATH DE number 3912424 (Why is no real title available?)
• Hamiltonian cycle curves in the space of discounted occupational measures
• Constructing dense graphs with unique Hamiltonian cycles
• Finding a Hamilton cycle fast on average using rotations and extensions
• Hidden Hamiltonian cycle recovery via linear programming
• Feasible Bases for a Polytope Related to the Hamilton Cycle Problem
• On approximating the longest path in a graph

This page was built for publication: Finding hidden hamiltonian cycles

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