Ir al contenido

Documat


On a binary distance model for the minimum linear arrangement problem

  • Gerhard Reinelt [1] ; Hanna Seitz [1]
    1. [1] Universität Heidelberg, Alemania
  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 22, Nº. 1, 2014, págs. 384-396
  • Idioma: inglés
  • Enlaces
  • Resumen
    • 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.


Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno