Approximating the Number of Acyclic Orientations for a Class of Sparse Graphs

DOI10.1017/S0963548303005844MaRDI QIDQ4812336zbMATH OpenOpenAlexFDO

Authors Magnus Bordewich

Publication date 7 September 2004

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548303005844

zbMATH Keywords

Tutte polynomial

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• Approximating the Tutte polynomial
• Inapproximability of the Tutte polynomial
• Inapproximability of the Tutte polynomial of a planar graph
• scientific article; zbMATH DE number 1369835

Cited in

(4)

• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• Dominic Welsh: his work and influence

This page was built for publication: Approximating the Number of Acyclic Orientations for a Class of Sparse Graphs

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