|
Computational Discrete Optimization CO 759, Winter 2015 HW1: Implementing Kruskal's MST algorithm Model for the C code Makefile -- use to build the code from seperate files kruskal_hw.c -- main file, without the actual spanning-tree code :) util.c -- utility routines; for now just a timing function util.h -- header file for the utility routines Test Graphs These graphs were created with the edgegen routine in Concorde, starting with geometric point sets. g10.22.edg -- 10 nodes, 22 edges, MST = 21 g100.1012.edg -- 100 nodes, 1012 edges, MST = 671 g1000.1647.edg -- 1000 nodes, 1647 edges, MST = 20817 g10000.18780.edg -- 10000 nodes, 18780 edges, MST = 654518 g100000.168747.edg -- 100000 nodes, 168747 edges, MST = 206919060 g100000.299967.edg -- 100000 nodes, 299967 edges, MST = 204918263 g1000000.1694628.edg -- 1000000 nodes, 1694628 edges, MST = 653899944 g1000000.11869219.edg -- 1000000 nodes, 11869219 edges, MST = 647691284 g10000000.29999959.edg.gz -- 10000000 nodes, 29999959 edges, MST = 20463694352 |
|