2026-07-23T04:16:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13337 2024-03-06T10:51:44Z ddc:004 open_access

PACE Solver Description: Bute-Plus: A Bottom-Up Exact Solver for Treedepth Trimble, James Treedepth Elimination Tree Graph Algorithms This note introduces Bute-Plus, an exact solver for the treedepth problem. The core of the solver is a positive-instance driven dynamic program that constructs an elimination tree of minimum depth in a bottom-up fashion. Three features greatly improve the algorithm’s run time. The first of these is a specialised trie data structure. The second is a domination rule. The third is a heuristic presolve step can quickly find a treedepth decomposition of optimal depth for many instances. Schloss Dagstuhl – Leibniz-Zentrum für Informatik James Trimble 2020 Is Part Of LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2020.34 urn:nbn:de:0030-drops-133371 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.34 eng https://creativecommons.org/licenses/by/3.0/legalcode