Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width
From MaRDI portal
Publication:3012830
DOI10.1007/978-3-642-22006-7_45zbMath1333.68288arXiv1102.3635OpenAlexW2122716720MaRDI QIDQ3012830
Ross J. Kang, Magnus Bordewich
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1102.3635
Markov chain Monte Carlotree-widthgraph polynomialscanonical pathsrapid mixingrandomised approximation schemessubset expansion
Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A two-variable interlace polynomial
- Fast evaluation of interlace polynomials on graphs of bounded treewidth
- Ising models on locally tree-like graphs
- Mixing time of critical Ising model on trees is polynomial in the height
- A multivariate interlace polynomial and its computation for graphs of bounded clique-width
- From a zoo to a zoology: Towards a general theory of graph polynomials
- Evaluating a weighted graph polynomial for graphs of bounded tree-width
- The vertex separation number of a graph equals its path-width
- A weighted graph polynomial from chromatic invariants of knots
- Farrell polynomials on graphs of bounded tree width
- An algorithm for the Tutte polynomials of graphs of bounded treewidth
- Glauber dynamics on trees and hyperbolic graphs
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- The mixing time of Glauber dynamics for coloring regular trees
- Graph Polynomials and Their Applications I: The Tutte Polynomial
- Graph Polynomials and Their Applications II: Interrelations and Interpretations
- Polynomial-Time Approximation Algorithms for the Ising Model
- Treewidth: Characterizations, Applications, and Computations
- Approximating the Partition Function of the Ferromagnetic Potts Model
- A polynomial invariant for knots via von Neumann algebras
- Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
- On the computational complexity of the Jones and Tutte polynomials
- Approximating the Number of Acyclic Orientations for a Class of Sparse Graphs
- Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
- On the Complexity of the Interlace Polynomial
- Fast mixing for independent sets, colorings, and other models on trees
- The Random-Cluster Model
- Time-Dependent Statistics of the Ising Model
- Monte Carlo sampling methods using Markov chains and their applications
- A Contribution to the Theory of Chromatic Polynomials
- A 3-approximation for the pathwidth of Halin graphs
