Hamiltonian Cycles and Subsets of Discounted Occupational Measures

References

• [1] Aigner M, Ziegler GM, Hofmann KH, Erdős P (2010) Proofs from the Book (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• [2] Altman E (1999) Constrained Markov Decision Processes, vol. 7 (CRC Press, Boca Raton, FL).Google Scholar
• [3] Applegate DL, Bixby RE, Chvatal V, Cook WJ (2011) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• [4] 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
• [5] Bollobás B (1984) The evolution of sparse graphs. Erdős P, Bollobás B, eds. Proc. Cambridge Combinatorial Conf. Graph Theory Combinatorics (Academic Press, London), 35–57.Google Scholar
• [6] Bollobás B (1998) Random graphs. Axler S, Gehring FW, Ribet KA, eds. Modern Graph Theory (Springer, New York), 215–252.Crossref, Google Scholar
• [7] Borkar VS, Filar JA (2011) Markov chains, Hamiltonian cycles and volumes of convex bodies. J. Global Optim. 55(3):633–639.Crossref, Google Scholar
• [8] 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
• [9] 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
• [10] 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
• [11] Ejov V, Litvak N, Nguyen GT, Taylor PG (2011) Proof of the Hamiltonicity-Trace conjecture for singularly perturbed Markov chains. J. Appl. Probab. 48(4):901–910.Crossref, Google Scholar
• [12] Eshragh A, Filar JA (2011) Hamiltonian cycles, random walks, and discounted occupational measures. Math. Oper. Res. 36(2):258–270.Link, Google Scholar
• [13] 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
• [14] Feinberg EA (2000) Constrained discounted Markov decision processes and Hamiltonian cycles. Math. Oper. Res. 25(1):130–140.Link, Google Scholar
• [15] Filar JA, Krass D (1994) Hamiltonian cycles and Markov chains. Math. Oper. Res. 19(1):223–237.Link, Google Scholar
• [16] Filar JA, Moeini A (2019) Hamiltonian cycle curves in the space of discounted occupational measures. Ann. Oper. Res., ePub ahead of print October 14, https://doi.org/10.1007/s10479-015-2030-2.Google Scholar
• [17] 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
• [18] Jerrum M (2003) Counting, Sampling and Integrating: Algorithms and Complexity (Springer Science & Business Media, Berlin, Heidelberg).Crossref, Google Scholar
• [19] Kallenberg LCM (1983) Linear Programming and Finite Markovian Control Problems, Mathematical Centre Tracts, vol. 148 (Mathematical Centre, Amsterdam).Google Scholar
• [20] Litvak N, Ejov V (2009) Markov chains and optimality of the Hamiltonian cycle. Math. Oper. Res. 34(1):71–82.Link, Google Scholar
• [21] Łuczak T (1991) Size and connectivity of the k-core of a random graph. Discrete Math. 91(1):61–68.Crossref, Google Scholar
• [22] Puterman ML (2014) Markov Decision Processes: Discrete Stochastic Dynamic Programming (John Wiley & Sons, Hoboken, NJ).Google Scholar