### Abstract

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.

Original language | English |
---|---|

Article number | 6 |

Pages (from-to) | 1-12 |

Number of pages | 12 |

Journal | ACM Transactions on Computation Theory |

Volume | 8 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1 May 2016 |

Externally published | Yes |

## Fingerprint Dive into the research topics of 'Tractable Parameterizations for the Minimum Linear Arrangement Problem'. Together they form a unique fingerprint.

## Cite this

*ACM Transactions on Computation Theory*,

*8*(2), 1-12. [6]. https://doi.org/10.1145/2898352