Exact counting of Euler Tours for Graphs of Bounded Treewidth

P. Chebolu; M. Cryan; R. Martin

Exact counting of Euler Tours for Graphs of Bounded Treewidth

P. Chebolu, M. Cryan, R. Martin

Research output: Working paper

Abstract / Description of output

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).

Original language	English
Publisher	ArXiv
Number of pages	16
Publication status	Published - 1 Oct 2013

Keywords / Materials (for Non-textual outputs)

Computer Science - Discrete Mathematics, Mathematics - Combinatorics, 05C85, 68R10

Access to Document

http://arxiv.org/abs/1310.0185

Counting and Sampling of Lattice points in Polytopes.
Cryan, M.
EPSRC
1/03/06 → 30/11/09
Project: Research

Cite this

@techreport{abb1e78ab8094afc9436a24c36fa6a70,

title = "Exact counting of Euler Tours for Graphs of Bounded Treewidth",

abstract = "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). ",

keywords = "Computer Science - Discrete Mathematics, Mathematics - Combinatorics, 05C85, 68R10",

author = "P. Chebolu and M. Cryan and R. Martin",

year = "2013",

month = oct,

day = "1",

language = "English",

publisher = "ArXiv",

type = "WorkingPaper",

institution = "ArXiv",

}

TY - UNPB

T1 - Exact counting of Euler Tours for Graphs of Bounded Treewidth

AU - Chebolu, P.

AU - Cryan, M.

AU - Martin, R.

PY - 2013/10/1

Y1 - 2013/10/1

N2 - 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).

AB - 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).

KW - Computer Science - Discrete Mathematics, Mathematics - Combinatorics, 05C85, 68R10

M3 - Working paper

BT - Exact counting of Euler Tours for Graphs of Bounded Treewidth

PB - ArXiv

ER -

Exact counting of Euler Tours for Graphs of Bounded Treewidth

Abstract / Description of output

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

Counting and Sampling of Lattice points in Polytopes.

Cite this