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

DOI10.1017/S0963548303005844zbMath1103.68087MaRDI QIDQ4812336

Magnus Bordewich

Publication date: 7 September 2004

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

zbMATH Keywords

Tutte polynomial

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

68W20: Randomized algorithms