2026-07-24T09:27:36Z https://drops.dagstuhl.de/oai

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

PACE Solver Description: Tweed-Plus: A Subtree-Improving Heuristic Solver for Treedepth Trimble, James Treedepth Elimination Tree Heuristics 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. 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.35 urn:nbn:de:0030-drops-133382 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.35 eng https://creativecommons.org/licenses/by/3.0/legalcode