Hamiltonian completions of sparse random graphs

DOI10.1016/J.DAM.2005.05.001MaRDI QIDQ2576345zbMATH OpenOpenAlexFDO

Authors David Gamarnik, Maxim Sviridenko

Publication date 27 December 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.05.001

zbMATH Keywords

Hamiltonicitytravelling salesman problem

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• How many random edges make a dense graph hamiltonian?
• On the number of hamilton cycles in a random graph
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Finding Hamilton cycles in sparse random graphs
• An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three

Cites work

• A linear algorithm for the Hamiltonian completion number of the line graph of a tree
• Advances on the Hamiltonian Completion Problem
• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 3467157 (Why is no real title available?)
• scientific article; zbMATH DE number 2064410 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• On the optional hamiltonian completion problem
• The total interval number of a tree and the Hamiltonian completion number of its line graph

Cited in

(8)

• Evolutionary operators for the Hamiltonian completion problem
• Local search algorithms for finding the Hamiltonian completion number of line graphs
• Hamiltonian completion
• scientific article; zbMATH DE number 4031730 (Why is no real title available?)
• Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
• Euler index of uncertain random graph: concepts and properties
• Hamilton completion and the path cover number of sparse random graphs
• A lower bound on the Hamiltonian path completion number of a line graph

This page was built for publication: Hamiltonian completions of sparse random graphs

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