Counting Euler Tours in Undirected Bounded Treewidth Graphs
We show that counting Euler tours in undirected bounded tree-width graphs is tractable even in parallel - by proving a #SAC1 ⊆ NC2 ⊆ P upper bound. This is in stark contrast to #Pcompleteness of the same problem in general graphs. Our main technical contribution is to show how (an instance of) dynam...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2015
|