Linear ordering problems on graphs
Download
- Program: LinearOrdering.zip (to be used with SageMath).
- Data:
- Small part (in edgelist format) of the CMPLIB from the Optsicom Project. Computation results can be found below.
- Rome graphs in edgelist or in graphml format (see also the data section of the Graph Drawing homepage). Computation results can be found below.
References
- [Cou16] D. Coudert. A note on Integer Linear Programming formulations for linear ordering problems on graphs [Research Report] Inria; I3S; Universite Nice Sophia Antipolis; CNRS. 2016, pp.33. [https://hal.inria.fr/hal-01271838]
Small dataset
Below are the values computed for the bandwidth, cutwidth, and
pathwidth of graphs of the Small graphs (available in edgelist format)
from the CMPLIB
from the Optsicom
Project.
For each graph, we have been able to compute the optimal values
before the computation time limit (5 min).
These data are also available as a single json
file. The file also contains computed values for sumcut and
optimal linear arrangement (optimal or width of best found feasible solution).
| Name | Nodes | Edges | Pathwidth | Cutwidth | Bandwidth |
|---|
Rome graphs
Below are the values computed for the bandwidth, cutwidth and
pathwidth of the Rome graphs (available in edgelist
and graphml
formats) from the data section of the Graph Drawing homepage.
Reported values are best obtained, independently of the
ILP used. When the optimality of the solution has not been proven
in given computation time limit (5 min), we have reported the
width of the best
found feasible solution, if any.
These data are also available as a single json
file.
| Name | Nodes | Edges | Pathwidth | Upper Bound | Cutwidth | Upper Bound | Bandwidth | Upper Bound |
|---|