PACE Solver Description: Fluid

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

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 languageEnglish
Title of host publication15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
EditorsYixin Cao , Marcin Pilipczuk
Number of pages3
Volume180
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date04.12.2020
Pages27:1--27:3
ISBN (Print)978-3-95977-172-6
DOIs
Publication statusPublished - 04.12.2020
Event15th International Symposium on Parameterized and Exact Computation - Online Event, Hong Kong, Hong Kong
Duration: 14.12.202018.12.2020

DFG Research Classification Scheme

  • 409-01 Theoretical Computer Science

Fingerprint

Dive into the research topics of 'PACE Solver Description: Fluid'. Together they form a unique fingerprint.

Cite this