Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Tractable Parameterizations for the Minimum Linear Arrangement Problem

Fellows, Michael R., Hermelin, Danny, Rosamond, Frances A. and Shachnai, Hadas (2013). Tractable Parameterizations for the Minimum Linear Arrangement Problem. In: 21st Annual European Symposium ESA 2013, Sophia Antipolis, France, 2-4 September 2013.

Document type: Conference Paper

IRMA ID 82794376xPUB263
Author Fellows, Michael R.
Hermelin, Danny
Rosamond, Frances A.
Shachnai, Hadas
Title Tractable Parameterizations for the Minimum Linear Arrangement Problem
Conference Name 21st Annual European Symposium ESA 2013
Conference Location Sophia Antipolis, France
Conference Dates 2-4 September 2013
Conference Publication Title Lecture Notes in Computer Science 8125: Advanced Research in Computing and Software Science: Algorithms - ESA 2013, 21st Annual European Symposium
Place of Publication Germany
Publisher Springer
Publication Year 2013
Volume Number 8125 LNCS
ISBN 978-3-642-40449-8   (check CDU catalogue open catalogue search in new window)
ISSN 0302-9743   (check CDU catalogue open catalogue search in new window)
Start Page 457
End Page 468
Total Pages 12
HERDC Category E1 - Conference Publication (DIISR)
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.
Description for Link Link to conference homepage
Link publisher's homepage
URL http://algo2013.inria.fr/esa.shtml
http://link.springer.com/chapter/10.1007/978-3-642-40450-4_39
 
Versions
Version Filter Type
Access Statistics: 27 Abstract Views  -  Detailed Statistics
Created: Thu, 07 Aug 2014, 16:40:01 CST