Linear ordering problems on graphs
- Program: linear-ordering.zip (to be used with SageMath).
- [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]
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
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).
Below are the values computed for the bandwidth, cutwidth and
pathwidth of the Rome graphs (available in edgelist
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|