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.27
URN: urn:nbn:de:0030-drops-133300
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13330/
Bannach, Max ;
Berndt, Sebastian ;
Schuster, Martin ;
Wienöbst, Marcel
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.
BibTeX - Entry
@InProceedings{bannach_et_al:LIPIcs:2020:13330,
author = {Max Bannach and Sebastian Berndt and Martin Schuster and Marcel Wien{\"o}bst},
title = {{PACE Solver Description: Fluid}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {27:1--27:3},
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/13330},
URN = {urn:nbn:de:0030-drops-133300},
doi = {10.4230/LIPIcs.IPEC.2020.27},
annote = {Keywords: treedepth, heuristics}
}
