1 Search Results for "Stockhusen, Christoph"

Document
DOI: 10.4230/LIPIcs.IPEC.2015.224
Fast Parallel Fixed-parameter Algorithms via Color Coding

Authors: Max Bannach, Christoph Stockhusen, and Till Tantau

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
Fixed-parameter algorithms have been successfully applied to solve numerous difficult problems within acceptable time bounds on large inputs. However, most fixed-parameter algorithms are inherently sequential and, thus, make no use of the parallel hardware present in modern computers. We show that parallel fixed-parameter algorithms do not only exist for numerous parameterized problems from the literature - including vertex cover, packing problems, cluster editing, cutting vertices, finding embeddings, or finding matchings - but that there are parallel algorithms working in constant time or at least in time depending only on the parameter (and not on the size of the input) for these problems. Phrased in terms of complexity classes, we place numerous natural parameterized problems in parameterized versions of AC^0. On a more technical level, we show how the color coding method can be implemented in constant time and apply it to embedding problems for graphs of bounded tree-width or tree-depth and to model checking first-order formulas in graphs of bounded degree.
Cite as

Max Bannach, Christoph Stockhusen, and Till Tantau. Fast Parallel Fixed-parameter Algorithms via Color Coding. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 224-235, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.IPEC.2015.224,
  author =	{Bannach, Max and Stockhusen, Christoph and Tantau, Till},
  title =	{{Fast Parallel Fixed-parameter Algorithms via Color Coding}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{224--235},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.224},
  URN =		{urn:nbn:de:0030-drops-55857},
  doi =		{10.4230/LIPIcs.IPEC.2015.224},
  annote =	{Keywords: color coding, parallel computation, fixed-parameter tractability, graph packing, cutting \$ell\$ vertices, cluster editing, tree-width, tree-depth,}
}
  • Refine by Author
  • 1 Bannach, Max
  • 1 Stockhusen, Christoph
  • 1 Tantau, Till

  • Refine by Classification

  • Refine by Keyword
  • 1 cluster editing
  • 1 color coding
  • 1 cutting $ell$ vertices
  • 1 fixed-parameter tractability
  • 1 graph packing
  • Show More...

  • 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