Feasible Bases for a Polytope Related to the Hamilton Cycle Problem

DOI10.1287/moor.2020.1112zbMath1484.90135arXiv1907.12691OpenAlexW3132799110MaRDI QIDQ5026442

Sogol Mohammadian, Thomas Kalinowski

Publication date: 8 February 2022

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.12691

zbMATH Keywords

polytoperandom walkHamilton cyclefeasible basis

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Markov and semi-Markov decision processes (90C40) Random walks on graphs (05C81)

Cites Work

• Unnamed Item
• On transition matrices of Markov chains corresponding to Hamiltonian cycles
• A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• An interior point heuristic for the Hamiltonian cycle problem via Markov decision processes
• Markov chains, Hamiltonian cycles and volumes of convex bodies
• Constrained Discounted Markov Decision Processes and Hamiltonian Cycles
• Hamiltonian Cycles, Random Walks, and Discounted Occupational Measures
• Proof of the Hamiltonicity-Trace Conjecture for Singularly Perturbed Markov Chains
• Markov Chains and Optimality of the Hamiltonian Cycle
• Refined MDP-Based Branch-and-Fix Algorithm for the Hamiltonian Cycle Problem
• Determinants and Longest Cycles of Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Hamiltonian Cycles and Markov Chains
• Finding hidden hamiltonian cycles
• Hamiltonian Cycles and Subsets of Discounted Occupational Measures

This page was built for publication: Feasible Bases for a Polytope Related to the Hamilton Cycle Problem