File formats [formats.txt]

A program in C++ to verify the correctness of the solutions to the problem [v2ec.tgz]. The same program can be easily modified to output the cuts needed to derive the set covering formulation of the E1-2AUG problem.

Instances and Solutions

A suffix "pre" in the name indicates that instances are preprocessed and hence consist of a spanning tree + a set of augmenting edges. Parallel edges may be present only between edges in the augmenting set and those in the spanning tree.

• Instances with uniform weights (to download all the instances use 'wget -r -l1 -nd --no-parent -A.gz' + link)
• Instances from uniform random graphs (The name is formed by U-[size]-[edge density]-[random seed]-[pre].ins).
• Instances from geometric random graphs (The name is formed by G-[size]-[edge density]-[random seed]-[pre].ins).
• Instances from Small World random graphs (The name is formed by sw-[size]-[D]-[p]-[random seed]-[pre].ins).
  Generator [small-world.py]
• Generator instances tree and cycle
• Instances with non-uniform weights (to download all the instances use 'wget -r -l1 -nd --no-parent -A.gz' + link)
• Instances from uniform random graphs (The name is formed by U-[size]-[edge density]-[random seed]-[pre].ins).
• Instances from geometric random graphs (The name is formed by G-[size]-[edge density]-[random seed]-[pre].ins).
• Instances from Small World random graphs (The name is formed by sw-[size]-[D]-[p]-[random seed]-[pre].ins).
  Generator [make_random_weights.py]
• Generator instances tree and cycle
• Instances form [Ljubic and Raidl, Evolutionary Local Search for the Edge-biconnectivity Augmentation Problem., Information Processing Letters, 82 (1), 39-45, 2002]. Details can be found at http://www.ads.tuwien.ac.at/research/NetworkDesign/Generator.html
  • Instances A3, B1, B6, D3, D5, M1, N1, N2, R1, R2, E1, E2, E3 and their solutions in our format. [ljubic.ins.zip, ljubic.aug.zip].
  • Instances derived from TSPLIB. An instance of E1-2AUG is derived from a TSP instance either by maintaining the complete graph or by selecting a percentage of nearest neighbors for each vertex. The spanning tree is the minimum spanning tree derived from the complete graph and it is maintained the same also when the graph is reduced to a percentage of nearest neighbors in the graph. The instances considered are lin318m0, lin318m10, pa561m0, pa561m10, pcb442m0, pcb442m10, pr226m0, pr226m15, pr439m0, pr439m10. Except the pa561m0 and pa561m10, they are all Euclidean instances. [tsplib.ins.zip, tsplib.aug.zip]

Gallery

Euclidean instance. Black edges are tree edges and red edges are augmenting edges.

Small World instance: sw-20-10-1-6. Red dashed edges are augmenting edges, bold edges are tree edges, blue dashed edges are edges selected for augmentation in an optimal solution:

Tree and cycle instance. Black edges are tree edges and red edges are augmenting edges.

External links

Small World graphs visualization (Frank van Ham, Jarke J. van Wijk, Andreas Noack, Jeff Heer, Tamara Munzner)

Small World graphs: Java Applet that Creates a Small World Graph with n Nodes (Angelos Stavrou)