TY - JOUR
T1 - Exact counting of Euler tours for generalized series-parallel graphs
AU - Chebolu, Prasad
AU - Cryan, Mary
AU - Martin, Russell
PY - 2012/1
Y1 - 2012/1
N2 - We give a simple polynomial-time algorithm to exactly count the number of Euler tours (ETs) of any Eulerian generalized series-parallel graph, and show how to adapt this algorithm to exactly sample a random ET of the given generalized series-parallel graph. Note that the class of generalized series-parallel graphs includes all outerplanar graphs. We can perform the counting in time O(mΔ3), where Δ is the maximum degree of the graph with m edges. We use O(mnΔ2logΔ) bits to store intermediate values during our computations. To date, these are the first known polynomial-time algorithms to count or sample ETs of any class of graphs; there are no other known polynomial-time algorithms to even approximately count or sample ETs of any other class of graphs. The problem of counting ETs is known to be #P-complete for general graphs (Brightwell and Winkler, 2005 [2]) also for planar graphs (Creed, 2010 [3]).
AB - We give a simple polynomial-time algorithm to exactly count the number of Euler tours (ETs) of any Eulerian generalized series-parallel graph, and show how to adapt this algorithm to exactly sample a random ET of the given generalized series-parallel graph. Note that the class of generalized series-parallel graphs includes all outerplanar graphs. We can perform the counting in time O(mΔ3), where Δ is the maximum degree of the graph with m edges. We use O(mnΔ2logΔ) bits to store intermediate values during our computations. To date, these are the first known polynomial-time algorithms to count or sample ETs of any class of graphs; there are no other known polynomial-time algorithms to even approximately count or sample ETs of any other class of graphs. The problem of counting ETs is known to be #P-complete for general graphs (Brightwell and Winkler, 2005 [2]) also for planar graphs (Creed, 2010 [3]).
KW - Euler tour
KW - Series-parallel graph
UR - http://www.scopus.com/inward/record.url?scp=84855563515&partnerID=8YFLogxK
U2 - 10.1016/j.jda.2011.03.011
DO - 10.1016/j.jda.2011.03.011
M3 - Article
VL - 10
SP - 110
EP - 122
JO - Journal of Discrete Algorithms
JF - Journal of Discrete Algorithms
SN - 1570-8667
IS - n/a
ER -