Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width

MaRDI QIDQ463068zbMATH OpenFDO

Authors Magnus Bordewich, Ross J. Kang

Publication date 23 October 2014

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

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p19

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Markov chain Monte Carloapproximate countingtree-widthgraph polynomialscanonical paths

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Graph polynomials (05C31) Approximation algorithms (68W25) Enumeration in graph theory (05C30) Hypergraphs (05C65) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Recommendations

• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• scientific article; zbMATH DE number 6469177
• Fast mixing for independent sets, colorings, and other models on trees
• Glauber dynamics on trees: Boundary conditions and mixing time
• The Glauber dynamics for colorings of bounded degree trees

Cites work

• scientific article; zbMATH DE number 1566488 (Why is no real title available?)
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 3784908 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 4121424 (Why is no real title available?)
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• scientific article; zbMATH DE number 6297817 (Why is no real title available?)
• scientific article; zbMATH DE number 3076589 (Why is no real title available?)
• A 3-approximation for the pathwidth of Halin graphs
• A Contribution to the Theory of Chromatic Polynomials
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A counterexample to rapid mixing of the Ge-Stefankovic process
• A graph polynomial for independent sets of bipartite graphs
• A multivariate interlace polynomial and its computation for graphs of bounded clique-width
• A polynomial invariant for knots via von Neumann algebras
• A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
• A two-variable interlace polynomial
• A weighted graph polynomial from chromatic invariants of knots
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Approximating the Number of Acyclic Orientations for a Class of Sparse Graphs
• Beitrag zur Theorie des Ferromagnetismus
• Evaluating a weighted graph polynomial for graphs of bounded tree-width
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• Farrell polynomials on graphs of bounded tree width
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• Fast mixing for independent sets, colorings, and other models on trees
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Generalized activities and the Tutte polynomial
• Geometric bounds for eigenvalues of Markov chains
• Glauber dynamics on trees and hyperbolic graphs
• Graph polynomials and their applications. I: The Tutte polynomial
• Graph polynomials and their applications. II: Interrelations and interpretations
• Graphs with small bandwidth and cutwidth
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Interlace polynomials
• Ising models on locally tree-like graphs
• Matroid Pathwidth and Code Trellis Complexity
• Matroid tree-width
• Mixing time of critical Ising model on trees is polynomial in the height
• On Markov Chains for Independent Sets
• On multivariate chromatic polynomials of hypergraphs and hyperedge elimination
• On the Complexity of the Interlace Polynomial
• On the computational complexity of the Jones and Tutte polynomials
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• Polynomial-Time Approximation Algorithms for the Ising Model
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• Simulation reductions for the Ising model
• Stopping Times, Metrics and Approximate Counting
• The Potts model and the Tutte polynomial.
• The Random-Cluster Model
• The Tutte Polynomial for Matroids of Bounded Branch-Width
• The mixing time of Glauber dynamics for coloring regular trees
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• The vertex separation number of a graph equals its path-width
• Time-Dependent Statistics of the Ising Model
• Tree-width, path-width, and cutwidth
• Treewidth: Characterizations, Applications, and Computations

Cited in

(2)

• Mixing of Markov chains for independent sets on chordal graphs with bounded separators
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width

This page was built for publication: Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width

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