Exact counting of Euler Tours for generalized series-parallel graphs

Details Exact counting of Euler Tours for generalized series-parallel graphs Exact counting of Euler Tours for generalized series-parallel graphs

2010-05-19

arxiv.org/abs/1005.3477v1

Computer Science

Data Structures and Algorithms

Article - 17 pages + Abstract - 1 page, 2 figures

Scientific paper

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 seriesparallel graphs includes all outerplanar graphs. We can perform the counting in time $O(m\Delta^3)$, where $\Delta$ is the maximum degree of the graph with $m$ edges. We use $O(m\Delta^2 \log \Delta)$ 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 [3]) and also for planar graphs (Creed, 2009 [4]).

Affiliated with

Also associated with

No associations

Rating

Exact counting of Euler Tours for generalized series-parallel graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exact counting of Euler Tours for generalized series-parallel graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact counting of Euler Tours for generalized series-parallel graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-480133