Tractable Parameterizations for the Minimum Linear Arrangement Problem

Michael Fellows, Danny Hermelin, Frances Rosamond, Hadas Shachnai

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

    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 languageEnglish
    Title of host publicationEuropean Symposium on Algorithms ESA 2013
    Subtitle of host publicationAlgorithms - ESA 2013, 21st Annual European Symposium
    EditorsHans Bodlaender, Giuseppe Italiano
    Place of PublicationGermany
    PublisherSpringer
    Pages457-468
    Number of pages12
    ISBN (Electronic)978-3-642-40450-4
    ISBN (Print)978-3-642-40449-8
    DOIs
    Publication statusPublished - 2013
    EventEuropean Symposium on Algorithms (ESA 2013 21st) - Sophia Antipolis, France, Sophia Antipolis, France
    Duration: 2 Sep 20134 Sep 2013
    Conference number: 2013 (21st)

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume8125

    Conference

    ConferenceEuropean Symposium on Algorithms (ESA 2013 21st)
    Abbreviated titleESA
    CountryFrance
    CitySophia Antipolis
    Period2/09/134/09/13

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

    Cite this