Publikation: Exact Approaches to Multi-Level Vertica...

Stammdaten
Titel: Exact Approaches to Multi-Level Vertical Orderings
Untertitel:
Kurzfassung: We present a semidefinite programming (SDP) approach for the problem of ordering vertices of a layered graph such that the edges of the graph are drawn as vertical as possible. This Multi-Level Vertical Ordering (MLVO) problem is a quadratic ordering problem and conceptually related to the well-studied problem of Multi-Level Crossing Minimization (MLCM). In contrast to the latter, it can be formulated such that it does not merely consist of multiple sequentially linked bilevel quadratic ordering problems, but as a genuine multi-level problem with dense cost matrix. This allows us to describe the graphs’ structures more compactly and therefore obtain solutions for graphs too large for MLCM in practice. In this paper we give a motivation and mathematical models for MLVO. We formulate linear and quadratic programs, including some strengthening constraint classes, and an SDP relaxation for MLVO. We compare all these approaches both theoretically and experimentally and show that MLVO’s properties render linear and quadratic programming approaches inapplicable, even for small sparse graphs, while the SDP works surprisingly well in practice. This is in stark contrast to other ordering problems like MLCM, where such graphs are typically solved more efficiently with integer linear programs. Finally, we also compare our approach to related MLCM approaches.
Schlagworte:
Publikationstyp: Beitrag in Zeitschrift (Autorenschaft)
Erscheinungsdatum: 14.03.2013 (Print)
Erschienen in: INFORMS Journal on Computing
INFORMS Journal on Computing
zur Publikation
 ( Institute for Operations Research and the Management Science (INFORMS); )
Titel der Serie: -
Bandnummer: 25
Heftnummer: 4
Erstveröffentlichung: Ja
Version: -
Seite: S. 611 - 624

Versionen
Keine Version vorhanden
Erscheinungsdatum:
ISBN (e-book): -
eISSN: -
DOI: http://dx.doi.org/10.1287/ijoc.1120.0525
Homepage: -
Open Access
  • Kein Open-Access
Erscheinungsdatum: 14.03.2013
ISBN: -
ISSN: 1091-9856
Homepage: -

AutorInnen
Philipp Hungerländer
Philipp.Hungerlaender@aau.at
Forschungsaktivitäten
zur Visitenkarte
(intern)

Zuordnung
Organisation Adresse
Fakultät für Technische Wissenschaften
  Institut für Mathematik
Universitätsstraße 65-67
9020 Klagenfurt am Wörthersee
Österreich
   math@aau.at
https://www.aau.at/mathematik
zur Organisation
Universitätsstraße 65-67
AT - 9020  Klagenfurt am Wörthersee

Kategorisierung
Sachgebiete
  • 1121 - Operations Research (5347, 5919)
Forschungscluster Kein Forschungscluster ausgewählt
Zitationsindex
  • Science Citation Index Expanded (SCI Expanded)
Informationen zum Zitationsindex: Master Journal List
Peer Reviewed
  • Ja
Publikationsfokus
  • Science to Science (Qualitätsindikator: I)
Klassifikationsraster der zugeordneten Organisationseinheiten:
Arbeitsgruppen Keine Arbeitsgruppe ausgewählt

Kooperationen
Keine Partnerorganisation ausgewählt

Beiträge der Publikation
Keine verknüpften Publikationen vorhanden