Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
From MaRDI portal
Publication:4845083
Combinatorial aspects of matroids and geometric lattices (05B35) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graph theory (including graph drawing) in computer science (68R10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)
Recommendations
Cites work
- A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
- A spanning tree expansion of the Jones polynomial
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- Acyclic orientations of graphs
- Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
- 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?)
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- On the computational complexity of the Jones and Tutte polynomials
- On the Principal Edge Tripartition of a Graph
- The complexity of colouring problems on dense graphs
- The Computational Complexity of the Tutte Plane: the Bipartite Case
Cited in
(27)- 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
- On the algebraic complexity of some families of coloured Tutte polynomials
- Evaluations of Tutte polynomials of regular graphs
- On the \(k\)-edge-incident subgraph problem and its variants
- The Potts model and the Tutte polynomial.
- Graphs with many strong orientations
- Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
- Mixing of the Glauber dynamics for the ferromagnetic Potts model
- Inapproximability of the Tutte polynomial
- On the quantum complexity of evaluating the Tutte polynomial
- Sparse reliable graph backbones
- Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
- scientific article; zbMATH DE number 1369835 (Why is no real title available?)
- Approximating the Number of Acyclic Orientations for a Class of Sparse Graphs
- scientific article; zbMATH DE number 795115 (Why is no real title available?)
- Edge-selection heuristics for computing Tutte polynomials
- Approximately counting embeddings into random graphs
- Parameterized Counting and Cayley Graph Expanders
- Dominic Welsh: his work and influence
- Dominic Welsh, 1938--2023
- Exploiting dense structures in parameterized complexity
- Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
- On the exact evaluation of certain instances of the Potts partition function by quantum computers
- Inapproximability of the Tutte polynomial
- A little statistical mechanics for the graph theorist
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)
