Abstract
In this note the Hamiltonian cycle problem is mapped into an infinite horizon discounted cost constrained Markov decision problem. The occupation measure based linear polytope associated with this control problem defines a convex set which either strictly contains or is equal to another convex set, depending on whether the underlying graph has a Hamiltonian cycle or not. This allows us to distinguish Hamiltonian graphs from non-Hamiltonian graphs by comparing volumes of two convex sets.
Original language | English |
---|---|
Pages (from-to) | 633-639 |
Number of pages | 7 |
Journal | Journal of Global Optimization |
Volume | 55 |
Issue number | 3 |
Early online date | 2013 |
DOIs | |
Publication status | Published - 2013 |
Keywords
- Discounted cost
- Hamiltonian cycle problem
- Markov decision process
- Uniform sampling
- Volumes of convex sets