LIPIcs.IPEC.2020.30.pdf
- Filesize: 382 kB
- 4 pages
Document
PACE Solver Description: SMS
Author
-
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
Cite As Get BibTex
Tuukka Korhonen. PACE Solver Description: SMS. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 30:1-30:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.30
Abstract
We describe SMS, our submission to the exact treedepth track of PACE 2020. SMS computes the treedepth of a graph by branching on the Small Minimal Separators of the graph.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
Keywords
- Treedepth
- PACE 2020
- SMS
- Minimal separators
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Anne Berry, Jean-Paul Bordat, and Olivier Cogis. Generating all the minimal separators of a graph. International Journal of Foundations of Computer Science, 11(3):397-403, 2000. URL: https://doi.org/10.1142/S0129054100000211.
- Anne Berry, Jean-Paul Bordat, Pinar Heggernes, Geneviève Simonet, and Yngve Villanger. A wide-range algorithm for minimal triangulation from an arbitrary ordering. Journal of Algorithms, 58(1):33-66, 2006. URL: https://doi.org/10.1016/j.jalgor.2004.07.001.
- Hans L. Bodlaender and Arie M. C. A. Koster. Treewidth computations II. Lower bounds. Information and Computation, 209(7):1103-1119, 2011. URL: https://doi.org/10.1016/j.ic.2011.04.003.
- Jitender S. Deogun, Ton Kloks, Dieter Kratsch, and Haiko Müller. On the vertex ranking problem for trapezoid, circular-arc and other graphs. Discrete Applied Mathematics, 98(1-2):39-63, 1999. URL: https://doi.org/10.1016/S0166-218X(99)00179-1.
- Philippe Galinier, Michel Habib, and Christophe Paul. Chordal graphs and their clique graphs. In Manfred Nagl, editor, Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science, volume 1017 of Lecture Notes in Computer Science, pages 358-371. Springer, 1995. URL: https://doi.org/10.1007/3-540-60618-1_88.
- Yasuaki Kobayashi and Hisao Tamaki. Treedepth parameterized by vertex cover number. In Jiong Guo and Danny Hermelin, editors, Proceedings of the 11th International Symposium on Parameterized and Exact Computation, volume 63 of LIPIcs, pages 18:1-18:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.IPEC.2016.18.
- Tuukka Korhonen. PACE 2020 exact treedepth submission: SMS, 2020. URL: https://doi.org/10.5281/zenodo.3872898.
- Alejandro A. Schäffer. Optimal node ranking of trees in linear time. Information Processing Letters, 33(2):91-96, 1989. URL: https://doi.org/10.1016/0020-0190(89)90161-0.
- Hisao Tamaki. Computing treewidth via exact and heuristic lists of minimal separators. In Ilias Kotsireas, Panos M. Pardalos, Konstantinos E. Parsopoulos, Dimitris Souravlias, and Arsenis Tsokas, editors, Proceedings of the Special Event on Analysis of Experimental Algorithms, volume 11544 of Lecture Notes in Computer Science, pages 219-236. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-34029-2_15.