TY - JOUR
T1 - Tractable Parameterizations for the Minimum Linear Arrangement Problem
AU - Fellows, Michael R.
AU - Hermelin, Danny
AU - Rosamond, Frances
AU - Shachnai, Hadas
PY - 2016/5/1
Y1 - 2016/5/1
N2 - The Minimum Linear Arrangement (MLA) problem involves embedding a given graph on the integer line so that the sum of the edge lengths of the embedded graph is minimized. Most layout problems are either intractable or not known to be tractable, parameterized by the treewidth of the input graph. We investigate MLA with respect to three parameters that provide more structure than treewidth. In particular, we give a factor (1 + ϵ)-approximation algorithm for MLA parameterized by (ϵ, k), where k is the vertex cover number of the input graph. By a similar approach, we obtain two FPT algorithms that exactly solve MLA parameterized by, respectively, the max leaf and edge clique cover numbers of the input graph.
AB - The Minimum Linear Arrangement (MLA) problem involves embedding a given graph on the integer line so that the sum of the edge lengths of the embedded graph is minimized. Most layout problems are either intractable or not known to be tractable, parameterized by the treewidth of the input graph. We investigate MLA with respect to three parameters that provide more structure than treewidth. In particular, we give a factor (1 + ϵ)-approximation algorithm for MLA parameterized by (ϵ, k), where k is the vertex cover number of the input graph. By a similar approach, we obtain two FPT algorithms that exactly solve MLA parameterized by, respectively, the max leaf and edge clique cover numbers of the input graph.
KW - Fixed parameter tractability
KW - MINIMUM LINEAR ARRANGEMENT
KW - Parameterized algorithms
UR - http://www.scopus.com/inward/record.url?scp=84969963442&partnerID=8YFLogxK
U2 - 10.1145/2898352
DO - 10.1145/2898352
M3 - Article
AN - SCOPUS:84969963442
VL - 8
SP - 1
EP - 12
JO - ACM Transactions on Computation Theory
JF - ACM Transactions on Computation Theory
SN - 1942-3454
IS - 2
M1 - 6
ER -