2026-08-16T21:59:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24573 2025-12-16T14:01:00Z ddc:004 open_access

Optimal Antimatroid Sorting Berendsohn, Benjamin Aram sorting working-set heap greedy antimatroid The classical comparison-based sorting problem asks us to find the underlying total ordering of a given set of elements, where we can only access the elements via comparisons. In this paper, we study a restricted version, where, as a hint, a set T of possible total orderings is given, usually in some compressed form. Recently, an algorithm called topological heapsort with optimal running time was found for case where T is the set of topological orderings of a given directed acyclic graph, or, equivalently, T is the set of linear extensions of a partial ordering [Haeupler et al. 2024]. We show that a simple generalization of topological heapsort is applicable to a much broader class of restricted sorting problems, where T corresponds to a given antimatroid. As a consequence, we obtain optimal algorithms for the following restricted sorting problems, where the allowed total orders are … - … restricted by a given set of monotone precedence formulas; - … the perfect elimination orders of a given chordal graph; or - … the possible vertex search orders of a given connected rooted graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Aram Berendsohn 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.104 urn:nbn:de:0030-drops-245735 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.104 eng https://creativecommons.org/licenses/by/4.0/legalcode