文章基本信息

标题：Width Notions for Ordering-Related Problems
本地全文：下载
作者：Emmanuel Arrighi ; Henning Fernau ; Mateus de Oliveira Oliveira 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：182
页码：1-18
DOI：10.4230/LIPIcs.FSTTCS.2020.9
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Parameterized algorithms; interval width; linear extension; one-sided crossing minimization; Kemeny rank aggregation; grouping by swapping