LIPIcs.IPEC.2020.35.pdf
- Filesize: 308 kB
- 4 pages
Document
PACE Solver Description: Tweed-Plus: A Subtree-Improving Heuristic Solver for Treedepth
Author
James Trimble 
-
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
Many thanks to the program committee of PACE 2020 and the optil.io team for an enjoyable contest.
Cite As Get BibTex
James Trimble. PACE Solver Description: Tweed-Plus: A Subtree-Improving Heuristic Solver for Treedepth. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 35:1-35:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.35
Abstract
This paper introduces Tweed-Plus, a heuristic solver for the treedepth problem. The solver uses two well-known algorithms to create an initial elimination tree: nested dissection (making use of the Metis library) and the minimum-degree heuristic. After creating an elimination tree of the entire input graph, the solver continues to apply nested dissection and the minimum-degree heuristic to parts of the graph with the aim of replacing subtrees of the elimination tree with alternatives of lower depth.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
- Theory of computation → Algorithm design techniques
Keywords
- Treedepth
- Elimination Tree
- Heuristics
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Alan George and Joseph W. H. Liu. The evolution of the minimum degree ordering algorithm. SIAM Review, 31(1):1-19, 1989. URL: https://doi.org/10.1137/1031001.
- George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Scientific Computing, 20(1):359-392, 1998. URL: https://doi.org/10.1137/S1064827595287997.
- Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. J. Symb. Comput., 60:94-112, 2014. URL: https://doi.org/10.1016/j.jsc.2013.09.003.
- Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
- Fernando Sánchez Villaamil. About treedepth and related notions. PhD thesis, RWTH Aachen University, Germany, 2017. URL: https://tcs.rwth-aachen.de/~sanchez/about-treedepth-and-related-notions.pdf.