scientific article; zbMATH DE number 1885142

Publication date: 19 March 2003

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Markov chain mixing time coupling colouring algorithm approximate counting path coupling sampling approximately at random volume of convex body

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Markov processes (60Jxx)

Related Items

On the approximation of one Markov chain by another, Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs, Counting and sampling $H$-colourings, Sampling colourings of the triangular lattice, A Dichotomy Theorem for Polynomial Evaluation, Randomly coloring planar graphs with fewer colors than the maximum degree, Efficient importance sampling for binary contingency tables, Fixed Precision MCMC Estimation by Median of Products of Averages, Finding a Level Ideal of a Poset, Counting Candy Crush configurations, On enumerating monomials and other combinatorial structures by polynomial interpolation, Inapproximability of the Tutte polynomial of a planar graph, Spectral independence, coupling, and the spectral gap of the Glauber dynamics, Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs, The Swendsen–Wang dynamics on trees, Correlation decay and the absence of zeros property of partition functions, Sampling from the low temperature Potts model through a Markov chain on flows, Finding Paths between Graph Colourings: Computational Complexity and Possible Distances, Simple permutations mix even better, Path coupling using stopping times and counting independent sets and colorings in hypergraphs, Parameterised counting in logspace, Young tableaux with periodic walls: counting with the density method, On some Tutte polynomial sequences in the square lattice, Mixing 3-Colourings in Bipartite Graphs, Discrete Optimal Transport with Independent Marginals is #P-Hard, The complexity of counting Eulerian tours in 4-regular graphs, Expander graphs and their applications, Markov chains, Hamiltonian cycles and volumes of convex bodies, Parameterized random complexity, An Inequality for Functions on the Hamming Cube, The switch Markov chain for sampling irregular graphs and digraphs, Hamiltonian Cycles and Subsets of Discounted Occupational Measures, A Markov chain on the solution space of edge colorings of bipartite graphs, Some Problems on Approximate Counting in Graphs and Matroids, The flip Markov chain for connected regular graphs, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, Structure and eigenvalues of heat-bath Markov chains, Location of zeros for the partition function of the Ising model on bounded degree graphs, Modified log-Sobolev inequalities for strongly log-concave distributions, Perfect simulation for a class of positive recurrent Markov chains, Path coupling without contraction, Inapproximability of the Tutte polynomial, Randomized approximation scheme and perfect sampler for closed Jackson networks with multiple servers, On eigenvalues of random complexes, The worm process for the Ising model is rapidly mixing, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, Connectedness of the graph of vertex-colourings, Entropy-driven cutoff phenomena, Random bichromatic matchings, Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#$P$-complete, Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains, Systematic scan for sampling colorings, Mixing of Markov chains for independent sets on chordal graphs with bounded separators, Counting independent sets in graphs with bounded bipartite pathwidth, Incremental delay enumeration: space and time, Randomly coloring random graphs, Microscopic path structure of optimally aligned random sequences, Graph classes and the switch Markov chain for matchings, Matrix norms and rapid mixing for spin systems, The Computational Complexity of Estimating MCMC Convergence Time, Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity, Solving and sampling with many solutions, Approximability of the eight-vertex model, Integrating and Sampling Cuts in Bounded Treewidth Graphs, Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Approximately counting bases of bicircular matroids, Mixing 3-colourings in bipartite graphs, Counting Weighted Independent Sets beyond the Permanent, Mixing time of Markov chains for the 1-2 model, Solving and sampling with many solutions: Satisfiability and other hard problems, Randomly coloring sparse random graphs with fewer colors than the maximum degree, Dynamic Sampling from Graphical Models, Simple permutations mix well, Combinatorial generation via permutation languages. I. Fundamentals, Polymer dynamics via cliques: new conditions for approximations, Random partition models and complementary clustering of Anglo-Saxon place-names