PACE Solver Description: PID*

Max Bannach; Sebastian Berndt; Martin Schuster; Marcel Wienöbst

doi:10.4230/LIPIcs.IPEC.2020.28

PACE Solver Description: PID*

Max Bannach, Sebastian Berndt, Martin Schuster, Marcel Wienöbst

Institut für Theoretische Informatik

3 Zitate (Scopus)

Abstract

This document provides a short overview of our treedepth solver PID⋆ in the version that we submitted to the exact track of the PACE challenge 2020. The solver relies on the positive-instance driven dynamic programming (PID) paradigm that was discovered in the light of earlier iterations of the PACE in the context of treewidth. It was recently shown that PID can be used to solve a general class of vertex pursuit-evasion games – which include the game theoretic characterization of treedepth. Our solver PID⋆ is build on top of this characterization.

Originalsprache	Englisch
Titel	15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Redakteure/-innen	Yixin Cao, Marcin Pilipczuk
Seitenumfang	4
Band	180
Herausgeber (Verlag)	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Erscheinungsdatum	04.12.2020
Seiten	28:1--28:4
ISBN (Print)	978-3-95977-172-6
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2020.28
Publikationsstatus	Veröffentlicht - 04.12.2020
Veranstaltung	15th International Symposium on Parameterized and Exact Computation - Online Event, Hong Kong, Hong Kong Dauer: 14.12.2020 → 18.12.2020

UN SDGs

Dieser Output leistet einen Beitrag zu folgendem(n) Ziel(en) für nachhaltige Entwicklung

SDG 9 – Industrie, Innovation und Infrastruktur

DFG-Fachsystematik

4.43-01 Theoretische Informatik

Dokumente

10.4230/LIPIcs.IPEC.2020.28

Zitieren

Bannach, M., Berndt, S., Schuster, M., & Wienöbst, M. (2020). PACE Solver Description: PID*. in Y. Cao, & M. Pilipczuk (Hrsg.), 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) (Band 180, S. 28:1--28:4). (Leibniz International Proceedings in Informatics (LIPIcs); Band 180). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2020.28

@inproceedings{d2fd0c31f6f64760a61590437dca87c0,

title = "PACE Solver Description: PID*",

abstract = "This document provides a short overview of our treedepth solver PID⋆ in the version that we submitted to the exact track of the PACE challenge 2020. The solver relies on the positive-instance driven dynamic programming (PID) paradigm that was discovered in the light of earlier iterations of the PACE in the context of treewidth. It was recently shown that PID can be used to solve a general class of vertex pursuit-evasion games – which include the game theoretic characterization of treedepth. Our solver PID⋆ is build on top of this characterization.",

author = "Max Bannach and Sebastian Berndt and Martin Schuster and Marcel Wien{\"o}bst",

year = "2020",

month = dec,

day = "4",

doi = "10.4230/LIPIcs.IPEC.2020.28",

language = "English",

isbn = "978-3-95977-172-6",

volume = "180",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "28:1----28:4",

editor = "Cao, \{Yixin \} and Pilipczuk, \{Marcin \}",

booktitle = "15th International Symposium on Parameterized and Exact Computation (IPEC 2020)",

note = "15th International Symposium on Parameterized and Exact Computation , IPEC 2020 ; Conference date: 14-12-2020 Through 18-12-2020",

}

Bannach, M, Berndt, S, Schuster, M & Wienöbst, M 2020, PACE Solver Description: PID*. in Y Cao & M Pilipczuk (Hrsg.), 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Bd. 180, Leibniz International Proceedings in Informatics (LIPIcs), Bd. 180, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, S. 28:1--28:4, 15th International Symposium on Parameterized and Exact Computation , Hong Kong, Hong Kong, 14.12.20. https://doi.org/10.4230/LIPIcs.IPEC.2020.28

PACE Solver Description: PID*. / Bannach, Max; Berndt, Sebastian; Schuster, Martin et al.
15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Hrsg. / Yixin Cao; Marcin Pilipczuk. Band 180 Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. S. 28:1--28:4 (Leibniz International Proceedings in Informatics (LIPIcs); Band 180).

Publikation: Kapitel in Büchern/Berichten/Konferenzbänden › Konferenzbeitrag › Begutachtung

TY - GEN

T1 - PACE Solver Description: PID*

AU - Bannach, Max

AU - Berndt, Sebastian

AU - Schuster, Martin

AU - Wienöbst, Marcel

PY - 2020/12/4

Y1 - 2020/12/4

N2 - This document provides a short overview of our treedepth solver PID⋆ in the version that we submitted to the exact track of the PACE challenge 2020. The solver relies on the positive-instance driven dynamic programming (PID) paradigm that was discovered in the light of earlier iterations of the PACE in the context of treewidth. It was recently shown that PID can be used to solve a general class of vertex pursuit-evasion games – which include the game theoretic characterization of treedepth. Our solver PID⋆ is build on top of this characterization.

AB - This document provides a short overview of our treedepth solver PID⋆ in the version that we submitted to the exact track of the PACE challenge 2020. The solver relies on the positive-instance driven dynamic programming (PID) paradigm that was discovered in the light of earlier iterations of the PACE in the context of treewidth. It was recently shown that PID can be used to solve a general class of vertex pursuit-evasion games – which include the game theoretic characterization of treedepth. Our solver PID⋆ is build on top of this characterization.

U2 - 10.4230/LIPIcs.IPEC.2020.28

DO - 10.4230/LIPIcs.IPEC.2020.28

M3 - Conference contribution

SN - 978-3-95977-172-6

VL - 180

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 28:1--28:4

BT - 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

A2 - Cao, Yixin

A2 - Pilipczuk, Marcin

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 15th International Symposium on Parameterized and Exact Computation

Y2 - 14 December 2020 through 18 December 2020

ER -