LIPIcs.IPEC.2020.36.pdf
- Filesize: 383 kB
- 4 pages
Document
PACE Solver Description: Sallow: A Heuristic Algorithm for Treedepth Decompositions
Author
Marcin Wrochna 
-
Part of:
Volume:
15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
File
Document Identifiers
Author Details
Acknowledgements
The author is very grateful to the https://pacechallenge.org/2020 organizers at the University of Warsaw, organizers of past editions, and the OPTIL.io team at the Poznań University of Technology for making this challenge possible.
Cite AsGet BibTex
Marcin Wrochna. PACE Solver Description: Sallow: A Heuristic Algorithm for Treedepth Decompositions. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 36:1-36:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.36
https://doi.org/10.4230/LIPIcs.IPEC.2020.36
Abstract
We describe a heuristic algorithm for computing treedepth decompositions, submitted for the https://pacechallenge.org/2020 challenge. It relies on a variety of greedy algorithms computing elimination orderings, as well as a Divide & Conquer approach on balanced cuts obtained using a from-scratch reimplementation of the 2016 FlowCutter algorithm by Hamann & Strasser [Michael Hamann and Ben Strasser, 2018].
Subject Classification
ACM Subject Classification
- Theory of computation → Discrete optimization
- Mathematics of computing → Solvers
- Mathematics of computing → Graph theory
Keywords
- treedepth
- decomposition
- heuristic
- weak colouring numbers
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Stefan Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey. BIT Numerical Mathematics, 25(1):2–23, 1985. URL: https://doi.org/10.1007/BF01934985.
- Michael Hamann and Ben Strasser. Graph bisection with pareto optimization. ACM Journal of Experimental Algorithmics, 23, 2018. URL: https://doi.org/10.1145/3173045.
- Jaroslav Nešetřil and Patrice Ossona de Mendez. Bounded height trees and tree-depth. In Sparsity, pages 115-144. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4_6.
- Ben Strasser. Computing tree decompositions with flowcutter: PACE 2017 submission. CoRR, abs/1709.08949, 2017. URL: http://arxiv.org/abs/1709.08949.
- Robert Endre Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. J. ACM, 31(2):245-281, 1984. URL: https://doi.org/10.1145/62.2160.
- Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, and Sebastian Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. Eur. J. Comb., 66:129-144, 2017. URL: https://doi.org/10.1016/j.ejc.2017.06.019.