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

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

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

(3)

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

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)