Refined MDP-based branch-and-fix algorithm for the Hamiltonian cycle problem

DOI10.1287/MOOR.1090.0398MaRDI QIDQ3169065zbMATH OpenOpenAlexFDO

Authors Michael Haythorpe, Giang T. Nguyen, Vladimir Ejov, Jerzy Filar

Publication date 27 April 2011

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2328/26401

zbMATH Keywords

branch-and-bound algorithmHamiltonian cyclesMarkov decision processesHCPHamilton cycle pronblem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Eulerian and Hamiltonian graphs (05C45) Markov and semi-Markov decision processes (90C40)

Recommendations

• A non-standard branch and bound method for the Hamiltonian cycle problem
• An interior point heuristic for the Hamiltonian cycle problem via Markov decision processes
• Hamiltonian cycle problem and Markov chains.
• Markov chains and optimality of the Hamiltonian cycle
• Constrained discounted Markov decision processes and Hamiltonian cycles.

Cited in

(10)

• On the fastest finite Markov processes
• Hamiltonian cycle curves in the space of discounted occupational measures
• Feasible Bases for a Polytope Related to the Hamilton Cycle Problem
• Adaptation of a branching algorithm to solve the multi-objective Hamiltonian cycle problem
• A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem
• A non-standard branch and bound method for the Hamiltonian cycle problem
• Markov chains, Hamiltonian cycles and volumes of convex bodies
• An interior point heuristic for the Hamiltonian cycle problem via Markov decision processes
• Proof of the hamiltonicity-trace conjecture for singularly perturbed Markov chains
• Hamiltonian cycles and subsets of discounted occupational measures

Describes a project that uses

Uses Software

• GENREG

This page was built for publication: Refined MDP-based branch-and-fix algorithm for the Hamiltonian cycle problem

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