License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2020.37
URN: urn:nbn:de:0030-drops-133404
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13340/
Go to the corresponding LIPIcs Volume Portal


Kowalik, Łukasz ; Mucha, Marcin ; Nadara, Wojciech ; Pilipczuk, Marcin ; Sorge, Manuel ; Wygocki, Piotr

The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth

pdf-format:
LIPIcs-IPEC-2020-37.pdf (0.6 MB)


Abstract

This year’s Parameterized Algorithms and Computational Experiments challenge (PACE 2020) was devoted to the problem of computing the treedepth of a given graph. Altogether 51 participants from 20 teams, 12 countries and 3 continents submitted their implementations to the competition. In this report, we describe the setup of the challenge, the selection of benchmark instances and the ranking of the participating teams. We also briefly discuss the approaches used in the submitted solvers and the differences in their performance on our benchmark dataset.

BibTeX - Entry

@InProceedings{kowalik_et_al:LIPIcs:2020:13340,
  author =	{Łukasz Kowalik and Marcin Mucha and Wojciech Nadara and Marcin Pilipczuk and Manuel Sorge and Piotr Wygocki},
  title =	{{The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Yixin Cao and Marcin Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13340},
  URN =		{urn:nbn:de:0030-drops-133404},
  doi =		{10.4230/LIPIcs.IPEC.2020.37},
  annote =	{Keywords: computing treedepth, contest, implementation challenge, FPT}
}

Keywords: computing treedepth, contest, implementation challenge, FPT
Collection: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Issue Date: 2020
Date of publication: 04.12.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI