Tractable Parameterizations for the Minimum Linear Arrangement Problem | Zendy

Michael R. Fellows | Zendy; Danny Hermelin | Zendy; Frances Rosamond | Zendy; Hadas Shachnai | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Tractable Parameterizations for the Minimum Linear Arrangement Problem

Author(s) -

Michael R. Fellows,

Danny Hermelin,

Frances Rosamond,

Hadas Shachnai

Publication year - 2016

Publication title -

acm transactions on computation theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.973

H-Index - 17

eISSN - 1942-3462

pISSN - 1942-3454

DOI - 10.1145/2898352

Subject(s) - treewidth , parameterized complexity , vertex cover , combinatorics , mathematics , edge cover , line graph , discrete mathematics , pathwidth , embedding , graph , clique sum , split graph , computer science , artificial intelligence

The Minimum Linear Arrangement (MLA) problem asks to embed 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 graphs. We investigate MLA with respect to three parameters that provide more structure than treewidth. In particular, we give a factor (1 + e)-approximation algorithm for MLA parameterized by (e, k), where k is the vertex cover number of the input graph. By a similar approach, we describe two FPT algorithms that exactly solve MLA parameterized by, respectively, the max leaf and edge clique cover numbers of the input graph.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research