Hamiltonian cycle problem and Markov chains.

DOI10.1007/978-1-4614-3232-6MaRDI QIDQ663172zbMATH OpenOpenAlexFDO

Authors Vivek Borkar, Jerzy Filar, Giang T. Nguyen, Vladimir Ejov

Publication date 14 February 2012

Published in International Series in Operations Research & Management Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-1-4614-3232-6

zbMATH Keywords

graph theoryMarkov chainsMarkov decision processesHamiltonian cycle problemcombinatorial programming

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Management decision making, including multiple objectives (90B50) Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Graph theory (05C99)

Recommendations

• Controlled Markov Chains, Graphs, and Hamiltonicity
• Markov chains and optimality of the Hamiltonian cycle
• Markov chains, Hamiltonian cycles and volumes of convex bodies
• Hamiltonian Cycles and Markov Chains
• An algorithm for finding Hamilton paths and cycles in random graphs

Cited in

(19)

• scientific article; zbMATH DE number 1560329 (Why is no real title available?)
• Refined MDP-based branch-and-fix algorithm for the Hamiltonian cycle problem
• Markov chains and optimality of the Hamiltonian cycle
• On the fastest finite Markov processes
• The buck-passing game
• Constructing families of cospectral regular graphs
• Analysis of Markov influence graphs
• Enumeration of unlabeled uniform hypergraphs
• On transition matrices of Markov chains corresponding to Hamiltonian cycles
• A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem
• Finding Hamiltonian cycles using an interior point method
• 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
• Deterministic ``snakes and ladders heuristic for the Hamiltonian cycle problem
• Constrained discounted Markov decision processes and Hamiltonian cycles.
• On the Hamiltonicity gap and doubly stochastic matrices
• Proof of the hamiltonicity-trace conjecture for singularly perturbed Markov chains
• A note on using the resistance-distance matrix to solve Hamiltonian cycle problem

This page was built for publication: Hamiltonian cycle problem and Markov chains.

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