2013/10/01 by Prasad Chebolu, Chebolu, Prasad, Mary Cryan +3 · 1 citation
Computer Science · Mathematics · #05C85 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Markov Chains and Monte Carlo Methods #cs.DM #math.CO #msc:05C85 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1310.0185
16 pages, draft
arxiv created 2013/10/01 · openalex publication_date 2013/10/01 · arxiv updated 2013/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we give a simple polynomial-time algorithm to exactly count the number of Euler Tours (ETs) of any Eulerian graph of bounded treewidth. The problems of counting ETs are known to be #P-complete for general graphs (Brightwell and Winkler, (Brightwell and Winkler, 2005). To date, no polynomial-time algorithm for counting Euler tours of any class of graphs is known except for the very special case of series-parallel graphs (which have treewidth 2).