On a binary distance model for the minimum linear arrangement problem

Gerhard Reinelt () and Hanna Seitz

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2014, vol. 22, issue 1, 384-396

Abstract: The minimum linear arrangement problem consists of finding an embedding of the nodes of a graph on the line such that the sum of the resulting edge lengths is minimized. The problem is among the classical NP-hard optimization problems and there has been extensive research on exact and approximative algorithms. In this paper, we introduce a new model based on binary variables d ijk that are equal to 1 if nodes i and j have distance k in the ordering. We analyze this model and point to connections and differences to a model using integer distance variables. Based on computational experiments, we argue that our model is worth further theoretical and practical investigation and that is has potentials yet to be examined. Copyright Sociedad de Estadística e Investigación Operativa 2014

Keywords: Linear arrangement problem; Graph layout; Integer programming; 90C10; 90C27; 90C57 (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s11750-012-0263-7 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:22:y:2014:i:1:p:384-396

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-012-0263-7

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().