Institut[e] f(o|ü)r Informati(cs|k), [Universität] Osnabrück [University]
Here, you can find the benchmark sets used in our study of heuristics, as well as, linear, quadratic, and semidefinite programs to solve Multi-level Verticality Optimization problems. Detailed descriptions can be found in the papers:
|MLVO, Proper level graphs, narrow alignment scheme||mlvm.proper.narrow.tar.gz|
|MLVO, Proper level graphs, wide alignment scheme||mlvm.proper.wide.tar.gz|
|MLVO, Non-proper level graphs, narrow alignment scheme||mlvm.nonproper.narrow.tar.gz|
|MLVO, Non-proper level graphs, wide alignment scheme||mlvm.nonproper.wide.tar.gz|
|MLCVO (hence: Proper level graphs, narrow alignment scheme)||mlcvo.tar.gz|
Each package contains all the instances of the groups Polytope, Graphviz, and Other. The node order given in these files is the order of the optimal (or best known) solution, as reported in the paper. You may also be interested in corresponding multi-level crossing minimization results.
Rome graphs and North DAGs instances: identical to the ones of the MLCM study.
You may want to use (free for private and academic use, no liability!) the the following python-scripts to generate SVGs from the raw solution files.
The package-files contain simple text files, each text file is a single instance.
For proper level graphs, the format is as follows:
<Number-of-Levels> <Number-of-Edges-Between-First-and-Second-Level> <Number-of-Edges-Between-Second-and-Third-Level> ... <Number-of-Nodes-on-First-Level> <Type-of-Node-0> <Type-of-Node-1> <Type-of-Node-2> ... <Number-of-Nodes-on-Second-Level> <Type-of-Node-0> <Type-of-Node-1> <Type-of-Node-2> ... ... <Index-of-Node-on-First-Level> <Index-of-Node-on-Second-Level> <Index-of-Node-on-First-Level> <Index-of-Node-on-Second-Level> ... <Index-of-Node-on-Second-Level> <Index-of-Node-on-Third-Level> ...
Thereby, the 2-tuples describe the edges in the graph. The node indices start with 0 on each layer. A node is either of type "1" (original node), "0" (positional dummy) or "-1" (long-edge dummy).
For non-proper level graphs, the format is as follows:
<Number-of-Levels> <Number-of-Edges> <Number-of-Nodes-on-First-Level> <Number-of-Nodes-on-Second-Level> ... <Index-of-Node> <Index-of-Node> ...
Thereby, the 2-tuples describe the edges in the graph. The node indices, starting with 0 on the first layer, are sequential over all layers. A node is either of type "1" (original node), or "0" (positional dummy). The edges are always going from a lower to a higher layer.