.png){kind=icon}
.png){kind=icon}
Return
Width notions for ordering-related problems
.png){kind=icon}
OA
AI
DOI：10.1016/j.jcss.2026.103777.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We are studying a weighted version of a linear extension problem, given some finite partial order rho, 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 rho which corresponds to the pathwidth of the cocomparability graph of rho. COMPLETION OF AN ORDERING 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 rho. We also relate the interval width of rho (when rho is derived from such an application problem) 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 subexponential-time algorithms for ordering problems. (c) 2026 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords:
Parameterized algorithms
Interval width
Linear extension
One-sided crossing minimization
Kemeny rank aggregation
Grouping by swapping
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
J
IF:
0.9
Papers:
51
Citations:
4.5K