Feasible Bases for a Polytope Related to the Hamilton Cycle Problem

References

• [1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms and Applications (Pearson, Prentice Hall, Upper Saddle River, NJ).Google Scholar
• [2] Applegate DL, Bixby RE, Chvátal V, Cook WJ (2011) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• [3] Avrachenkov K, Eshragh A, Filar JA (2016) On transition matrices of Markov chains corresponding to Hamiltonian cycles. Ann. Oper. Res. 243(1-2):19–35.Crossref, Google Scholar
• [4] Borkar VS, Filar JA (2011) Markov chains, Hamiltonian cycles and volumes of convex bodies. J. Global Optim. 55(3):633–639.Crossref, Google Scholar
• [5] Broder AZ, Frieze AM, Shamir E (1994) Finding hidden Hamiltonian cycles. Random Structures Algorithms 5(3):395–410.Crossref, Google Scholar
• [6] Ejov V, Filar JA, Gondzio J (2004) An interior point heuristic for the Hamiltonian cycle problem via Markov decision processes. J. Global Optim. 29(3):315–334.Crossref, Google Scholar
• [7] Ejov V, Filar JA, Haythorpe M, Nguyen GT (2009) Refined MDP-based branch-and-fix algorithm for the Hamiltonian cycle problem. Math. Oper. Res. 34(3):758–768.Link, Google Scholar
• [8] Ejov V, Filar JA, Murray W, Nguyen GT (2008) Determinants and longest cycles of graphs. SIAM J. Discrete Math. 22(3):1215–1225.Crossref, Google Scholar
• [9] Ejov V, Litvak N, Nguyen GT, Taylor PG (2011) Proof of the Hamiltonicity-trace conjecture for singularly perturbed Markov chains. J. Appl. Probab. 48(04):901–910.Crossref, Google Scholar
• [10] Eshragh A, Filar JA (2011) Hamiltonian cycles, random walks, and discounted occupational measures. Math. Oper. Res. 36(2):258–270.Link, Google Scholar
• [11] Eshragh A, Filar JA, Haythorpe M (2011) A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem. Ann. Oper. Res. 189(1):103–125.Crossref, Google Scholar
• [12] Eshragh A, Filar JA, Kalinowski T, Mohammadian S (2020) Hamiltonian cycles and subsets of discounted occupational measures. Math. Oper. Res. 45(2):713–731.Link, Google Scholar
• [13] Feinberg EA (2000) Constrained discounted Markov decision processes and Hamiltonian cycles. Math. Oper. Res. 25(1):130–140.Link, Google Scholar
• [14] Filar JA, Krass D (1994) Hamiltonian cycles and Markov chains. Math. Oper. Res. 19(1):223–237.Link, Google Scholar
• [15] Filar JA, Moeini A (2021) Hamiltonian cycle curves in the space of discounted occupational measures. Ann. Oper. Res. Forthcoming.Google Scholar
• [16] Garey MR, Johnson DS, Tarjan RE (1976) The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4):704–714.Crossref, Google Scholar
• [17] Litvak N, Ejov V (2009) Markov chains and optimality of the Hamiltonian cycle. Math. Oper. Res. 34(1):71–82.Link, Google Scholar
• [18] Plesn’ik J (1979) The NP-completeness of the Hamiltonian cycle problem in planar diagraphs with degree bound two. Inform. Processing Lett. 8(4):199–201.Crossref, Google Scholar