2010/05/19 by Prasad Chebolu, Chebolu, Prasad, Mary Cryan +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1005.3477
Article - 17 pages + Abstract - 1 page, 2 figures
arxiv created 2010/05/19 · arxiv updated 2015/03/16
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Δ3), where Δ is the maximum degree of the graph with m edges. We use O(mΔ2 log Δ) 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]).