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

DOI10.1002/RSA.3240060409zbMATH Open0839.68074OpenAlexW2005687471WikidataQ29393798 ScholiaQ29393798MaRDI QIDQ4845083FDOQ4845083

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

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

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)

Cites Work

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

Cited In (23)

• The polytope of win vectors
• Title not available (Why is that?)
• 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
• Edge-selection heuristics for computing Tutte polynomials
• Forests, colorings and acyclic orientations of the square lattice
• Graphs with many strong orientations
• Title not available (Why is that?)
• On the algebraic complexity of some families of coloured Tutte polynomials
• Approximately counting embeddings into random graphs
• Evaluations of Tutte polynomials of regular graphs
• On the exact evaluation of certain instances of the Potts partition function by quantum computers
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• The Potts model and the Tutte polynomial.
• 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)