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 | |
| 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 |
DFG Research Classification Scheme
- 4.43-01 Theoretical Computer Science
