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

DOI10.1017/S0963548303005844zbMath1103.68087OpenAlexW2128995068MaRDI QIDQ4812336

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

Related Items (2)

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