Output details
11 - Computer Science and Informatics
University of Edinburgh
Output title
Exact counting of Euler Tours for Graphs of Bounded Treewidth
Type
U - Working paper
Platform
ArXiv
Year of publication
2013
Number of additional authors
2
Additional information
<12> Originality: This is the first polynomial-time algorithm for counting Euler tours (ETs) on graphs of bounded treewidth.
Significance: For many combinatorial structures, the number of these structures can be directly characterised as some point of the Tutte polynomial. It is well known that any point of the Tutte polynomial can be evaluated in polynomial-time on graphs of bounded treewidth. This paper shows that although ETs do not correspond to any point on the Tutte polynomial, there is also a polynomial-time algorithm to count ETs on bounded treewidth graphs.
Rigour: Full proofs are given in the paper.
Interdisciplinary
-
Cross-referral requested
-
Research group
F - Laboratory for Foundations of Computer Science
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
