Instance | Objective | Original graph | Reduced graph | ||
---|---|---|---|---|---|
|V| | |E| | |V| | |E| | ||
CELAR 01 | Minimum Order | 916 | 5,548 | ||
CELAR 02 | Minimum Order | 200 | 1,235 | ||
CELAR 03 | Minimum Order | 400 | 2,760 | ||
CELAR 04 | Minimum Order | 680 | 3,967 | ||
CELAR 05 | Minimum Span | 400 | 2,598 | ||
CELAR 06 | Minimum Interference | 200 | 1,322 | 100 | 350 |
CELAR 07 | Minimum Interference | 400 | 2,865 | 200 | 817 |
CELAR 08 | Minimum Interference | 916 | 5,744 | 458 | 1,655 |
CELAR 09 | Minimum Interference | 680 | 4,103 | 340 | 1,130 |
CELAR 10 | Minimum Interference | 680 | 4,103 | 340 | 1,130 |
CELAR 11 | Minimum Order | 680 | 4,103 | ||
GRAPH 01 | Minimum Order | 200 | 1,134 | ||
GRAPH 02 | Minimum Order | 400 | 2,245 | ||
GRAPH 03 | Minimum Span | 200 | 1,134 | ||
GRAPH 04 | Minimum Span | 400 | 2,244 | ||
GRAPH 05 | Minimum Interference | 200 | 1,134 | 100 | 416 |
GRAPH 06 | Minimum Interference | 400 | 2,170 | 200 | 843 |
GRAPH 07 | Minimum Interference | 400 | 2,170 | 200 | 843 |
GRAPH 08 | Minimum Order | 680 | 3,757 | ||
GRAPH 09 | Minimum Order | 916 | 5,246 | ||
GRAPH 10 | Minimum Span | 680 | 3,907 | ||
GRAPH 11 | Minimum Interference | 680 | 3,757 | 340 | 1,425 |
GRAPH 12 | Minimum Interference | 680 | 4,017 | 340 | 1,255 |
GRAPH 13 | Minimum Interference | 916 | 5,273 | 458 | 1,877 |
GRAPH 14 | Minimum Order | 916 | 4,638 |
Each instance is distributed in four files in a single directory.
instance | lower bounds | optimal value (range) | upper bounds | ||||||||||||||
[Aardal et al., 1996] | [Aardal et al., 1996] | [Aardal et al., 1996] | [Aardal et al., 1996] | [Tiourine et al., 1999] | [Kolen et al., 1994] | [Kolen et al., 1994] | [Tiourine et al., 1999] | [Tiourine et al., 1999] | [Tiourine et al., 1999] | [Bouju et al., 1995b] | [Bouju et al., 1995b] | [Kapsalis et al., 1995] | [Warners et al., 1997] | [Pasechnik, 1998] | [Crisan and Mühlenbein, 1998] | ||
clique bound | coloring number | generalized coloring number | linear programming relaxation | clique bound | constraint satisfaction | constraint satisfaction | simulated annealing | variable depth search | tabu search | tabu search | GENET | genetic algorithm | potential reduction | gradient descent | evolutionary search | ||
CELAR 01 | 12 | 14 | 16 | 16 | 14 | 16 | 16 | 16 | 16 | 16 | 16 | 18 | 16 | 20 | 16 | 16 | - |
CELAR 02 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 |
CELAR 03 | 12 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 16 | 16 | 14 | 14 |
CELAR 04 | - | - | - | 46 | 46 | 46 | 46 | 46 | 46 | 46 | 46 | 46 | 46 | 46 | 46 | 46 | - |
CELAR 11 | 20 | 20 | 20 | 22 | 22 | 22 | 22 | 22 | 24 | 24 | 22 | 24 | 24 | 32 | - | 22 | - |
GRAPH 01 | - | - | - | 18 | 18 | 18 | 18 | 18 | - | - | 18 | 18 | 18 | 20 | 18 | 18 | 18 |
GRAPH 02 | - | - | - | 14 | 14 | 14 | 14 | 14 | - | - | 14 | 16 | 14 | 16 | 14 | 14 | 14 |
GRAPH 08 | - | - | - | - | 16 | - | 16-18 | - | - | - | 20 | 24 | 22 | - | 18 | 18 | - |
GRAPH 09 | - | - | - | - | 18 | 18 | 18 | 18 | - | - | 22 | 22 | 22 | 28 | 18 | 18 | - |
GRAPH 14 | - | - | - | - | 8 | - | 8 | 10 | - | - | 10 | 12 | - | 14 | 10 | 8 | - |
instance | lower bounds | upper bounds | ||||||
[Aardal et al., 1996] | [Tiourine et al., 1999] | [Kolen et al., 1994] | [Tiourine et al., 1999] | [Bouju et al., 1995a] | [Bouju et al., 1995b] | [Warners et al., 1997] | [Pasechnik, 1998] | |
linear programming | quadratic programming | constraint satisfaction | tabu search | tabu search | GENET | potential reduction | potential reduction | |
CELAR 05 | 792 | 792 | 792 | 792 | 792 | 792 | 792 | 792 |
GRAPH 03 | - | - | 380 | 380 | - | - | - | 380 |
GRAPH 04 | - | - | 394 | 394 | - | - | - | 394 |
GRAPH 10 | - | - | 394 | 394 | - | - | 394 | 394 |
instance | lower bounds | optimal value (range) | upper bounds | ||||||||||||
[Aardal et al., 1996] | [Tiourine et al., 1999] | [Givry et al., 1997] | [Koster, 1999, Koster et al., 2002] | [Koster, 1999, Koster et al., 2001] | [Cooper et al., 2008] | [Sanchez et al., 2009] | [Allouche et al., 2010] | [Kolen, 1999] | [Kapsalis et al., 1995] | [Tiourine et al., 1999] | [Tiourine et al., 1999] | [Warners et al., 1997] | [Pasechnik, 1998] | ||
linear programming | quadratic programming | constraint satisfaction | tree decomposition | integer programming | constraint satisfaction | constraint satisfaction / tree deco | tree decomposition / parallel DP | genetic algorithm | genetic algorithm | simulated annealing | variable depth search | potential reduction | potential reduction | ||
CELAR 06 | 5 | - | 3,389 | 3,389 | 2,321 | 3,389 | 3,389 | 3,389 | 3,389 | 3,389 | 3,456 | 3,671 | 3,532 | 4,539 | 4,564 |
CELAR 07 | 5 | - | - | 300,000 | 180,525 | - | 343,592 | 343,592 | 343,592 | 343,592 | 1,670,572 | 567,949 | 344,103 | - | 831,926 |
CELAR 08 | - | - | - | 87 | 150 | - | - | 262 | 262 | 262 | 612 | 276 | 299 | - | 533 |
CELAR 09 | - | 14,969 | - | 15,571 | 15,571 | - | 15,571 | 15,571 | 15,599 | 15,571 | 15,573 | 15,775 | 15,770 | ||
CELAR 10 | - | 31,204 | - | 31,516 | 31,516 | - | 31,516 | 31,516 | 31,517 | 31,516 | 31,516 | 32,460 | 31,517 | ||
GRAPH 05 | - | - | - | 221 | 221 | - | 221 | 221 | 293 | 223 | - | - | 452 | ||
GRAPH 06 | - | - | - | 4,123 | 4,123 | - | 4,123 | 4,123 | 16,020 | 4,189 | - | - | 15,047 | ||
GRAPH 07 | - | - | - | 4,324 | 4,324 | - | 4,324 | 4,324 | 5,990 | 4,324 | - | - | 14,183 | ||
GRAPH 11 | - | - | - | 2,553 | 3,016 | 3,080 | 3,080 | 3,080 | 30,312 | 3,513 | - | - | 14,692 | ||
GRAPH 12 | - | - | - | 11,827 | 11,827 | - | 11,827 | 11,827 | 15,208 | 11,827 | - | - | 17,372 | ||
GRAPH 13 | - | - | - | 8,676 | 9,925 | 10,110 | 10,110 | 10,110 | 49,205 | 11,130 | - | - | 41,784 |