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

zbMATH Open1298.05284MaRDI QIDQ463068FDOQ463068

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

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

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

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)

Cites Work

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

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)