2026-07-23T19:07:48Z https://drops.dagstuhl.de/oai

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

Width Notions for Ordering-Related Problems Arrighi, Emmanuel Fernau, Henning de Oliveira Oliveira, Mateus Wolf, Petra Parameterized algorithms interval width linear extension one-sided crossing minimization Kemeny rank aggregation grouping by swapping We are studying a weighted version of a linear extension problem, given some finite partial order ρ, called Completion of an Ordering. While this problem is NP-complete, we show that it lies in FPT when parameterized by the interval width of ρ. This ordering problem can be used to model several ordering problems stemming from diverse application areas, such as graph drawing, computational social choice, or computer memory management. Each application yields a special ρ. We also relate the interval width of ρ to parameterizations such as maximum range that have been introduced earlier in these applications, sometimes improving on parameterized algorithms that have been developed for these parameterizations before. This approach also gives some practical sub-exponential time algorithms for ordering problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emmanuel Arrighi and Henning Fernau and Mateus de Oliveira Oliveira and Petra Wolf 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.9 urn:nbn:de:0030-drops-132505 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.9 eng https://creativecommons.org/licenses/by/3.0/legalcode