Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case

DOI10.1002/RSA.3240060409MaRDI QIDQ4845083zbMATH OpenOpenAlexWikidataFDO

Authors Noga Alon, Alan Frieze, D. J. A. Welsh

Publication date 28 May 1996

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.3240060409

zbMATH Keywords

polynomial randomised approximation schemesTutte-Gröthendieck polynomial

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Combinatorial aspects of matroids and geometric lattices (05B35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Recommendations

• scientific article; zbMATH DE number 795115
• scientific article; zbMATH DE number 1369835
• Inapproximability of the Tutte polynomial
• Inapproximability of the Tutte polynomial
• Approximating the Number of Acyclic Orientations for a Class of Sparse Graphs

Cites work

• scientific article; zbMATH DE number 1003265 (Why is no real title available?)
• scientific article; zbMATH DE number 177833 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1047748 (Why is no real title available?)
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• A spanning tree expansion of the Jones polynomial
• Acyclic orientations of graphs
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• On the Principal Edge Tripartition of a Graph
• On the computational complexity of the Jones and Tutte polynomials
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• The complexity of colouring problems on dense graphs

Cited in

(23)

• The polytope of win vectors
• scientific article; zbMATH DE number 1369835 (Why is no real title available?)
• Inapproximability of the Tutte polynomial
• Mixing of the Glauber dynamics for the ferromagnetic Potts model
• Sparse reliable graph backbones
• On the \(k\)-edge-incident subgraph problem and its variants
• Inapproximability of the Tutte polynomial
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• A little statistical mechanics for the graph theorist
• On the quantum complexity of evaluating the Tutte polynomial
• Approximating the Number of Acyclic Orientations for a Class of Sparse Graphs
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• Forests, colorings and acyclic orientations of the square lattice
• Edge-selection heuristics for computing Tutte polynomials
• Graphs with many strong orientations
• scientific article; zbMATH DE number 795115 (Why is no real title available?)
• On the algebraic complexity of some families of coloured Tutte polynomials
• Evaluations of Tutte polynomials of regular graphs
• Approximately counting embeddings into random graphs
• On the exact evaluation of certain instances of the Potts partition function by quantum computers
• The Potts model and the Tutte polynomial.
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• Parameterized Counting and Cayley Graph Expanders

This page was built for publication: Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case

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