PACE Solver Description: Fluid

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

doi:10.4230/LIPIcs.IPEC.2020.27

PACE Solver Description: Fluid

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

Institut für Theoretische Informatik

Abstract

This document describes the heuristic for computing treedepth decompositions of undirected graphs used by our solve fluid. The heuristic runs four different strategies to find a solution and finally outputs the best solution obtained by any of them. Two strategies are score-based and iteratively remove the vertex with the best score. The other two strategies iteratively search for vertex separators and remove them. We also present implementation strategies and data structures that significantly improve the run time complexity and might be interesting on their own.

Originalsprache	Englisch
Titel	15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Redakteure/-innen	Yixin Cao , Marcin Pilipczuk
Seitenumfang	3
Band	180
Herausgeber (Verlag)	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Erscheinungsdatum	04.12.2020
Seiten	27:1--27:3
ISBN (Print)	978-3-95977-172-6
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2020.27
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

DFG-Fachsystematik

409-01 Theoretische Informatik

UN SDGs

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

Zugriff auf Dokument

10.4230/LIPIcs.IPEC.2020.27

Zitieren

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

@inproceedings{51d072362f39453ba3fbf3457e7173cd,

title = "PACE Solver Description: Fluid",

abstract = "This document describes the heuristic for computing treedepth decompositions of undirected graphs used by our solve fluid. The heuristic runs four different strategies to find a solution and finally outputs the best solution obtained by any of them. Two strategies are score-based and iteratively remove the vertex with the best score. The other two strategies iteratively search for vertex separators and remove them. We also present implementation strategies and data structures that significantly improve the run time complexity and might be interesting on their own.",

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.27",

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 = "27:1----27:3",

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: Fluid. 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. 27:1--27:3, 15th International Symposium on Parameterized and Exact Computation , Hong Kong, Hong Kong, 14.12.20. https://doi.org/10.4230/LIPIcs.IPEC.2020.27

PACE Solver Description: Fluid. / 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. 27:1--27:3 (Leibniz International Proceedings in Informatics (LIPIcs); Band 180).

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

TY - GEN

T1 - PACE Solver Description: Fluid

AU - Bannach, Max

AU - Berndt, Sebastian

AU - Schuster, Martin

AU - Wienöbst, Marcel

PY - 2020/12/4

Y1 - 2020/12/4

N2 - This document describes the heuristic for computing treedepth decompositions of undirected graphs used by our solve fluid. The heuristic runs four different strategies to find a solution and finally outputs the best solution obtained by any of them. Two strategies are score-based and iteratively remove the vertex with the best score. The other two strategies iteratively search for vertex separators and remove them. We also present implementation strategies and data structures that significantly improve the run time complexity and might be interesting on their own.

AB - This document describes the heuristic for computing treedepth decompositions of undirected graphs used by our solve fluid. The heuristic runs four different strategies to find a solution and finally outputs the best solution obtained by any of them. Two strategies are score-based and iteratively remove the vertex with the best score. The other two strategies iteratively search for vertex separators and remove them. We also present implementation strategies and data structures that significantly improve the run time complexity and might be interesting on their own.

U2 - 10.4230/LIPIcs.IPEC.2020.27

DO - 10.4230/LIPIcs.IPEC.2020.27

M3 - Conference contribution

SN - 978-3-95977-172-6

VL - 180

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 27:1--27:3

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 -

PACE Solver Description: Fluid

Abstract

DFG-Fachsystematik

UN SDGs

Zugriff auf Dokument

Fingerprint

Zitieren