On Sampling Simple Paths in Planar Graphs According to Their Lengths

DOI10.1007/978-3-662-48054-0_41zbMath1471.60110OpenAlexW2406060353MaRDI QIDQ2946419

Sandro Montanari, Paolo Penna

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48054-0_41

zbMATH Keywords

Markov chainsampling simple paths

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Seven (lattice) paths to log-convexity
• Random generation of combinatorial structures from a uniform distribution
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Analysis of a nonreversible Markov chain sampler.
• Path coupling without contraction
• Self-testing algorithms for self-avoiding walks
• Markov Chain Algorithms for Planar Lattice Structures
• Randomly coloring constant degree graphs
• Randomly coloring random graphs
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Randomly coloring planar graphs with fewer colors than the maximum degree
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• The Complexity of Enumeration and Reliability Problems
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• On Markov Chains for Independent Sets
• Estimating the Number of s-t Paths in a Graph

This page was built for publication: On Sampling Simple Paths in Planar Graphs According to Their Lengths