Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs

DOI10.37236/9503zbMath1453.05056arXiv2011.09726OpenAlexW3106890812MaRDI QIDQ2213805

Viresh Patel, Fabian Stroh, Pieter Kleer

Publication date: 3 December 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

irreducibility of switch-based Markov chainsundirected dense graph

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Eulerian and Hamiltonian graphs (05C45) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Fast uniform generation of regular graphs
• Bipartite permutation graphs
• Towards random uniform sampling of bipartite graphs with given degree sequence
• Introduction to reconfiguration
• Complexity of Hamiltonian cycle reconfiguration
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• On the Switch Markov Chain for Perfect Matchings
• Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices
• Sampling Regular Graphs and a Peer-to-Peer Network
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Some Theorems on Abstract Graphs

This page was built for publication: Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs