1 Search Results for "Dzulfikar, M. Ayaz"


Document
Invited Paper
The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)

Authors: M. Ayaz Dzulfikar, Johannes K. Fichte, and Markus Hecher

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)


Abstract
The organizers of the 4th Parameterized Algorithms and Computational Experiments challenge (PACE 2019) report on the 4th iteration of the PACE challenge. This year, the first track featured the MinVertexCover problem, which asks given an undirected graph G=(V,E) to output a set S subseteq V of vertices such that for every edge vw in E at least one endpoint belongs to S. The exact decision version of this problem is one of the most discussed problem if not even the prototypical problem in parameterized complexity theory. Another two tracks were dedicated to computing the hypertree width of a given hypergraph, which is a certain generalization of tree decompositions to hypergraphs that has widely been applied to problems in databases, constraint programming, and artificial intelligence. On one track we asked for submissions that compute hypertree decompositions of minimum width (MinHypertreeWidth) and on the other track we asked to heuristically compute hypertree decompositions of small width quickly (HeurHypertreeWidth). We received 28 implementations from 26 teams. This year we asked participants to submit solver descriptions in order to count as a submission for the challenge. We received those from 16 teams with overall 33 participants from 10 countries. One team submitted successful solutions to all three tracks.

Cite as

M. Ayaz Dzulfikar, Johannes K. Fichte, and Markus Hecher. The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper). In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{dzulfikar_et_al:LIPIcs.IPEC.2019.25,
  author =	{Dzulfikar, M. Ayaz and Fichte, Johannes K. and Hecher, Markus},
  title =	{{The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{25:1--25:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.25},
  URN =		{urn:nbn:de:0030-drops-114861},
  doi =		{10.4230/LIPIcs.IPEC.2019.25},
  annote =	{Keywords: Parameterized Algorithms, Vertex Cover Problem, Hypertree Decompositions, Implementation Challenge, FPT}
}
  • Refine by Author
  • 1 Dzulfikar, M. Ayaz
  • 1 Fichte, Johannes K.
  • 1 Hecher, Markus

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Hypergraphs
  • 1 Mathematics of computing → Solvers
  • 1 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 FPT
  • 1 Hypertree Decompositions
  • 1 Implementation Challenge
  • 1 Parameterized Algorithms
  • 1 Vertex Cover Problem

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

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