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

Institute of Theoretical Computer Science

1 Citation (Scopus)

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.

Original language	English
Title of host publication	15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Editors	Yixin Cao , Marcin Pilipczuk
Number of pages	3
Volume	180
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date	04.12.2020
Pages	27:1--27:3
ISBN (Print)	978-3-95977-172-6
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2020.27
Publication status	Published - 04.12.2020
Event	15th International Symposium on Parameterized and Exact Computation - Online Event, Hong Kong, Hong Kong Duration: 14.12.2020 → 18.12.2020

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

DFG Research Classification Scheme

4.43-01 Theoretical Computer Science

Access to Document

10.4230/LIPIcs.IPEC.2020.27

Cite this

Bannach, M., Berndt, S., Schuster, M., & Wienöbst, M. (2020). PACE Solver Description: Fluid. In Y. Cao , & M. Pilipczuk (Eds.), 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) (Vol. 180, pp. 27:1--27:3). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 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 (eds), 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). vol. 180, Leibniz International Proceedings in Informatics (LIPIcs), vol. 180, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 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). ed. / Yixin Cao ; Marcin Pilipczuk. Vol. 180 Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. p. 27:1--27:3 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 180).

Research output: Chapters in Books/Reports/Conference Proceedings › Conference contribution › peer-review

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

UN SDGs

DFG Research Classification Scheme

Access to Document

Fingerprint

Cite this