On the Hamiltonicity Gap and doubly stochastic matrices

DOI10.1002/rsa.20237zbMath1208.05069OpenAlexW4231798900MaRDI QIDQ3055760

Vivek S. Borkar, Vladimir V. Ežov, Jerzy A. Filar

Publication date: 9 November 2010

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20237

zbMATH Keywords

singular perturbationHamiltonian cycleoptimal policycontrolled Markov chains

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Eulerian and Hamiltonian graphs (05C45) Stochastic matrices (15B51)

Related Items (7)

On transition matrices of Markov chains corresponding to Hamiltonian cycles ⋮ Data Uncertainty in Markov Chains: Application to Cost-Effectiveness Analyses of Medical Innovations ⋮ Consistent behavior of certain perturbed determinants induced by graphs ⋮ Proof of the Hamiltonicity-Trace Conjecture for Singularly Perturbed Markov Chains ⋮ On the fastest finite Markov processes ⋮ Hamiltonian cycle curves in the space of discounted occupational measures ⋮ The Buck-Passing Game

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Laurent expansion for a nearly singular matrix
• Inversion of Analytic Matrix Functions That are Singular at the Origin
• Constrained Discounted Markov Decision Processes and Hamiltonian Cycles
• Matrix Analysis
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Almost all regular graphs are hamiltonian
• Hamiltonian Cycles and Markov Chains
• Hamiltonian Cycles and Singularly Perturbed Markov Chains

This page was built for publication: On the Hamiltonicity Gap and doubly stochastic matrices