Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Approximating the number of acyclic orientations for a class of sparse graphs
Bordewich, M.
Authors
Abstract
The Tutte polynomial $T(G;x,y)$ of a graph evaluates to many interesting combinatorial quantities at various points in the $(x,y)$ plane, including the number of spanning trees, number of forests, number of acyclic orientations, the reliability polynomial, the partition function of the Q-state Potts model of a graph, and the Jones polynomial of an alternating link. The exact computation of $T(G;x,y)$ has been shown by Vertigan and Welsh \cite{vertiganandwelsh} to be \#P-hard at all but a few special points and on two hyperbolae, even in the restricted class of planar bipartite graphs. Attention has therefore been focused on approximation schemes. To date, positive results have been restricted to the upper half plane $y>1$, and most results have relied on a condition of sufficient denseness in the graph. In this paper we present an approach that yields a fully polynomial randomised approximation scheme for $T(G;x,y)$ for $x>1,\ y=1$, and for $T(G;2,0)$, in a class of sparse graphs. This is the first positive result that includes the important point $(2,0)$.
Citation
Bordewich, M. (2004). Approximating the number of acyclic orientations for a class of sparse graphs. Combinatorics, Probability and Computing, 13(1), 1-16. https://doi.org/10.1017/s0963548303005844
Journal Article Type | Article |
---|---|
Publication Date | 2004-01 |
Deposit Date | Jun 18, 2008 |
Publicly Available Date | Jun 18, 2008 |
Journal | Combinatorics, Probability and Computing |
Print ISSN | 0963-5483 |
Electronic ISSN | 1469-2163 |
Publisher | Cambridge University Press |
Peer Reviewed | Peer Reviewed |
Volume | 13 |
Issue | 1 |
Pages | 1-16 |
DOI | https://doi.org/10.1017/s0963548303005844 |
Keywords | Tutte polynomial, FPRAS, Approximation, Complexity. |
Files
Published Journal Article
(156 Kb)
PDF
Copyright Statement
© 2004 Cambridge University Press
You might also like
Evaluating Gaussian Grasp Maps for Generative Grasping Models
(2022)
Conference Proceeding
On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks
(2022)
Journal Article
On the Maximum Agreement Subtree Conjecture for Balanced Trees
(2022)
Journal Article
Autoencoders Without Reconstruction for Textural Anomaly Detection
(2021)
Conference Proceeding
Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss
(2021)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search