1 Search Results for "Ganesan, Venkatesh"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.246
Counting Euler Tours in Undirected Bounded Treewidth Graphs

Authors: Nikhil Balaji, Samir Datta, and Venkatesh Ganesan

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
We show that counting Euler tours in undirected bounded tree-width graphs is tractable even in parallel - by proving a GapL upper bound. This is in stark contrast to #P-completeness of the same problem in general graphs. Our main technical contribution is to show how (an instance of) dynamic programming on bounded clique-width graphs can be performed efficiently in parallel. Thus we show that the sequential result of Espelage, Gurski and Wanke for efficiently computing Hamiltonian paths in bounded clique-width graphs can be adapted in the parallel setting to count the number of Hamiltonian paths which in turn is a tool for counting the number of Euler tours in bounded tree-width graphs. Our technique also yields parallel algorithms for counting longest paths and bipartite perfect matchings in bounded-clique width graphs. While establishing that counting Euler tours in bounded tree-width graphs can be computed by non-uniform monotone arithmetic circuits of polynomial degree (which characterize #SAC^1) is relatively easy, establishing a uniform #SAC^1 bound needs a careful use of polynomial interpolation.
Cite as

Nikhil Balaji, Samir Datta, and Venkatesh Ganesan. Counting Euler Tours in Undirected Bounded Treewidth Graphs. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 246-260, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{balaji_et_al:LIPIcs.FSTTCS.2015.246,
  author =	{Balaji, Nikhil and Datta, Samir and Ganesan, Venkatesh},
  title =	{{Counting Euler Tours in Undirected Bounded Treewidth Graphs}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{246--260},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.246},
  URN =		{urn:nbn:de:0030-drops-56493},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.246},
  annote =	{Keywords: Euler Tours, Bounded Treewidth, Bounded clique-width, Hamiltonian cycles, Parallel algorithms}
}
  • Refine by Author
  • 1 Balaji, Nikhil
  • 1 Datta, Samir
  • 1 Ganesan, Venkatesh

  • Refine by Classification

  • Refine by Keyword
  • 1 Bounded Treewidth
  • 1 Bounded clique-width
  • 1 Euler Tours
  • 1 Hamiltonian cycles
  • 1 Parallel algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact