Abstract
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 + ε)-approximation algorithm for MLA parameterized by (ε, 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.
Original language | English |
---|---|
Title of host publication | European Symposium on Algorithms ESA 2013 |
Subtitle of host publication | Algorithms - ESA 2013, 21st Annual European Symposium |
Editors | Hans Bodlaender, Giuseppe Italiano |
Place of Publication | Germany |
Publisher | Springer |
Pages | 457-468 |
Number of pages | 12 |
ISBN (Electronic) | 978-3-642-40450-4 |
ISBN (Print) | 978-3-642-40449-8 |
DOIs | |
Publication status | Published - 2013 |
Event | European Symposium on Algorithms (ESA 2013 21st) - Sophia Antipolis, France, Sophia Antipolis, France Duration: 2 Sep 2013 → 4 Sep 2013 Conference number: 2013 (21st) |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 8125 |
Conference
Conference | European Symposium on Algorithms (ESA 2013 21st) |
---|---|
Abbreviated title | ESA |
Country/Territory | France |
City | Sophia Antipolis |
Period | 2/09/13 → 4/09/13 |