Finding Hamiltonian cycles using an interior point method

MaRDI QIDQ3062244zbMATH OpenFDO

Authors Michael Haythorpe

Publication date 3 January 2011

zbMATH Keywords

Hamiltonian cycle problemlogarithmic barrier algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Interior-point methods (90C51) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• An interior point heuristic for the Hamiltonian cycle problem via Markov decision processes
• An algorithm for finding Hamilton paths and cycles in random graphs
• A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem
• Markov chains, Hamiltonian cycles and volumes of convex bodies
• Hamiltonian cycle problem and Markov chains.

Cited in

(6)

• On the determinant and its derivatives of the rank-one corrected generator of a Markov chain on a graph
• Markov chains, Hamiltonian cycles and volumes of convex bodies
• Finding a Hamiltonian cycle by finding the global minimizer of a linearly constrained problem
• An interior point heuristic for the Hamiltonian cycle problem via Markov decision processes
• Proof of the hamiltonicity-trace conjecture for singularly perturbed Markov chains
• A note on using the resistance-distance matrix to solve Hamiltonian cycle problem

This page was built for publication: Finding Hamiltonian cycles using an interior point method

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