Tractable Parameterizations for the Minimum Linear Arrangement Problem

Michael Fellows; Danny Hermelin; Frances Rosamond; Hadas Shachnai

doi:10.1007/978-3-642-40450-4_39

Tractable Parameterizations for the Minimum Linear Arrangement Problem

Michael Fellows, Danny Hermelin, Frances Rosamond, Hadas Shachnai

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

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	https://doi.org/10.1007/978-3-642-40450-4_39
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

Access to Document

10.1007/978-3-642-40450-4_39

Cite this

Fellows, M., Hermelin, D., Rosamond, F., & Shachnai, H. (2013). Tractable Parameterizations for the Minimum Linear Arrangement Problem. In H. Bodlaender, & G. Italiano (Eds.), European Symposium on Algorithms ESA 2013: Algorithms - ESA 2013, 21st Annual European Symposium (pp. 457-468). (Lecture Notes in Computer Science ; Vol. 8125). Springer. https://doi.org/10.1007/978-3-642-40450-4_39

@inproceedings{ca5cc7bee4d747a689ca7f4f290dde36,

title = "Tractable Parameterizations for the Minimum Linear Arrangement Problem",

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.",

keywords = "Clique cover, Embedded graphs, FPT algorithms, Input graphs, Layout problems, Minimum linear arrangement, Parameterized, Three parameters, Approximation algorithms, Parameterization",

author = "Michael Fellows and Danny Hermelin and Frances Rosamond and Hadas Shachnai",

year = "2013",

doi = "10.1007/978-3-642-40450-4_39",

language = "English",

isbn = "978-3-642-40449-8",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "457--468",

editor = "Hans Bodlaender and Giuseppe Italiano",

booktitle = "European Symposium on Algorithms ESA 2013",

address = "Switzerland",

note = "European Symposium on Algorithms (ESA 2013 21st), ESA ; Conference date: 02-09-2013 Through 04-09-2013",

}

Fellows, M, Hermelin, D, Rosamond, F & Shachnai, H 2013, Tractable Parameterizations for the Minimum Linear Arrangement Problem. in H Bodlaender & G Italiano (eds), European Symposium on Algorithms ESA 2013: Algorithms - ESA 2013, 21st Annual European Symposium. Lecture Notes in Computer Science , vol. 8125, Springer, Germany, pp. 457-468, European Symposium on Algorithms (ESA 2013 21st), Sophia Antipolis, France, 2/09/13. https://doi.org/10.1007/978-3-642-40450-4_39

Tractable Parameterizations for the Minimum Linear Arrangement Problem. / Fellows, Michael; Hermelin, Danny; Rosamond, Frances et al.

European Symposium on Algorithms ESA 2013: Algorithms - ESA 2013, 21st Annual European Symposium. ed. / Hans Bodlaender; Giuseppe Italiano. Germany : Springer, 2013. p. 457-468 (Lecture Notes in Computer Science ; Vol. 8125).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

TY - GEN

T1 - Tractable Parameterizations for the Minimum Linear Arrangement Problem

AU - Fellows, Michael

AU - Hermelin, Danny

AU - Rosamond, Frances

AU - Shachnai, Hadas

N1 - Conference code: 2013 (21st)

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Clique cover

KW - Embedded graphs

KW - FPT algorithms

KW - Input graphs

KW - Layout problems

KW - Minimum linear arrangement

KW - Parameterized

KW - Three parameters

KW - Approximation algorithms

KW - Parameterization

UR - http://algo2013.inria.fr/esa.shtml

U2 - 10.1007/978-3-642-40450-4_39

DO - 10.1007/978-3-642-40450-4_39

M3 - Conference Paper published in Proceedings

SN - 978-3-642-40449-8

T3 - Lecture Notes in Computer Science

SP - 457

EP - 468

BT - European Symposium on Algorithms ESA 2013

A2 - Bodlaender, Hans

A2 - Italiano, Giuseppe

PB - Springer

CY - Germany

T2 - European Symposium on Algorithms (ESA 2013 21st)

Y2 - 2 September 2013 through 4 September 2013

ER -

Fellows M, Hermelin D, Rosamond F, Shachnai H. Tractable Parameterizations for the Minimum Linear Arrangement Problem. In Bodlaender H, Italiano G, editors, European Symposium on Algorithms ESA 2013: Algorithms - ESA 2013, 21st Annual European Symposium. Germany: Springer. 2013. p. 457-468. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-642-40450-4_39

Tractable Parameterizations for the Minimum Linear Arrangement Problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this