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

DOI10.1002/rsa.3240060409zbMath0839.68074OpenAlexW2005687471WikidataQ29393798 ScholiaQ29393798MaRDI QIDQ4845083

Noga Alon, Alan M. Frieze, Dominic 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) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

Mixing of the Glauber dynamics for the ferromagnetic Potts model, Unnamed Item, Sparse reliable graph backbones, Parameterized Counting and Cayley Graph Expanders, On the \(k\)-edge-incident subgraph problem and its variants, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, On the exact evaluation of certain instances of the Potts partition function by quantum computers, On the algebraic complexity of some families of coloured Tutte polynomials, Inapproximability of the Tutte polynomial, The Potts model and the Tutte polynomial, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, ON THE QUANTUM COMPLEXITY OF EVALUATING THE TUTTE POLYNOMIAL, A little statistical mechanics for the graph theorist, Approximately Counting Embeddings into Random Graphs, Graphs with Many Strong Orientations, The polytope of win vectors, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, Forests, colorings and acyclic orientations of the square lattice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• The complexity of colouring problems on dense graphs
• 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
• On the Principal Edge Tripartition of a Graph
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
• On the computational complexity of the Jones and Tutte polynomials
• A Theorem on Graphs, with an Application to a Problem of Traffic Control