Publication: Exact Approaches to Multi-Level Vertica...
Master data
| Title: | Exact Approaches to Multi-Level Vertical Orderings |
| Subtitle: | |
| Abstract: | 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. |
| Keywords: |
| Publication type: | Article in journal (Authorship) |
| Publication date: | 14.03.2013 (Print) |
| Published by: |
INFORMS Journal on Computing
INFORMS Journal on Computing
(
Institute for Operations Research and the Management Science (INFORMS);
)
to publication |
| Title of the series: | - |
| Volume number: | 25 |
| Issue: | 4 |
| First publication: | Yes |
| Version: | - |
| Page: | pp. 611 - 624 |
Versionen
| Keine Version vorhanden |
| Publication date: | |
| ISBN (e-book): | - |
| eISSN: | - |
| DOI: | http://dx.doi.org/10.1287/ijoc.1120.0525 |
| Homepage: | - |
| Open access |
|
| Publication date: | 14.03.2013 |
| ISBN: | - |
| ISSN: | 1091-9856 |
| Homepage: | - |
Authors
Assignment
| Organisation | Address | ||||
|---|---|---|---|---|---|
|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Categorisation
| Subject areas | |
| Research Cluster | No research Research Cluster selected |
| Citation index |
Information about the citation index: Master Journal List
|
| Peer reviewed |
|
| Publication focus |
Classification raster of the assigned organisational units:
|
| working groups | No working group selected |
Cooperations
No partner organisations selected
Research activities
All related research activities to this publication are shown here. With the link below, you can view them in the search view where you are also able to export them.
Show related search activities in search
| Projects: |
|
| Publications: | No related publications |
| Events: | No related events |
| Lectures: | No related lectures |
Articles of the publication
No related publications