Graph Isomorphism Algorithm Timings

          First in thread      Previous in thread

On June 8, I began to discuss my Graph Isomorphism algorithm (without really saying much about it, yet) and offered some very preliminary timing data.

Here is a summary of substantially more timing measurements for my graph isomorphism algorithm, implemented as a single-threaded application, running on an Intel Core 2 CPU 6400 @ 2.13 GHz with 3.25 GB of RAM. While my computer was busy with Folding@Home and letting me run a variety of programs, it was able to dedicate most of the time on one core to the graph isomorphism application.

The columns specify the range of probabilities of an edge in the randomly generated graphs.

The rows specify the range of the number of nodes in each graph.

The determination was correct and verified in all cases.

Graph Isomorphism algorithm duration in seconds to determine whether pairs of isomorphic graphs are isomorphic

    Results for 6292 pairs of isomorphic graphs

    Maximum duration
    Average duration
    Minimum duration
    Number of graph pairs

N \ pEdge	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
100 999	0.19 0.07 0.00 44	0.22 0.08 0.00 69	0.23 0.09 0.00 32	0.31 0.13 0.00 50	0.30 0.13 0.00 60	0.39 0.13 0.00 66	0.42 0.15 0.00 51	0.44 0.14 0.00 43	0.48 0.17 0.00 54	0.64 0.17 0.01 66
1000 1999	0.75 0.39 0.19 51	1.03 0.52 0.23 73	1.11 0.58 0.25 68	1.25 0.79 0.30 64	1.41 0.91 0.36 58	1.52 0.82 0.36 63	1.66 1.03 0.42 56	1.70 1.07 0.44 64	1.73 1.06 0.48 61	2.00 1.11 0.50 63
2000 2999	2.26 1.21 0.53 51	2.38 1.71 0.80 78	2.69 1.84 1.01 66	3.03 2.41 1.28 67	3.23 2.44 1.36 65	3.56 2.62 1.45 69	4.17 2.75 1.55 79	4.28 3.05 1.69 51	4.67 3.20 1.91 66	4.72 3.57 1.98 74
3000 3999	3.58 2.27 1.19 62	4.08 2.99 2.11 73	4.75 3.66 2.70 58	5.33 4.18 2.69 63	6.00 4.37 3.28 60	6.39 4.93 3.56 73	6.88 5.57 3.91 71	7.47 5.54 4.14 51	7.83 6.52 4.47 62	8.38 6.29 4.59 54
4000 4999	6.61 4.73 3.03 66	6.55 5.45 3.53 71	7.74 6.08 4.14 67	11.41 7.00 5.14 67	9.81 7.83 5.39 52	10.65 8.35 6.23 65	11.03 9.06 6.66 54	12.63 9.79 7.28 63	13.17 10.22 7.28 67	13.05 10.76 7.91 66
5000 5999	9.57 6.25 3.88 79	9.41 7.39 5.83 69	10.70 8.56 6.70 59	12.41 9.96 7.69 80	14.20 11.17 8.97 83	14.86 12.28 9.97 68	16.26 13.47 10.56 59	17.65 14.20 11.38 55	18.58 15.52 12.11 74	19.20 15.75 13.19 70
6000 6999	14.09 8.97 6.19 50	18.42 10.38 8.45 73	14.79 11.90 9.52 62	15.68 13.70 10.52 56	19.13 15.13 12.72 61	20.19 17.35 14.08 72	22.32 18.55 15.11 91	23.39 20.23 16.91 59	24.14 20.69 17.27 66	25.97 21.97 17.73 57
7000 7999	15.92 11.96 9.75 64	17.27 13.45 10.36 72	19.03 15.69 12.47 55	22.79 18.34 15.52 49	24.84 20.17 16.66 56	25.95 22.08 18.44 55	28.50 24.24 21.08 65	30.61 26.02 21.58 72	32.19 26.97 23.50 50	34.38 29.52 24.69 52
8000 8999	21.20 16.15 7.88 65	24.70 19.69 13.66 67	28.64 22.47 16.84 89	27.61 24.37 19.02 43	33.77 27.92 21.41 75	36.30 30.38 23.59 63	39.08 32.80 25.33 71	42.45 35.00 27.52 63	43.95 37.60 29.33 66	43.06 37.58 31.53 62
9000 9999	29.46 20.67 16.50 56	30.14 25.17 21.20 75	32.25 28.32 24.03 76	36.54 31.61 26.55 54	42.22 35.66 29.67 61	46.08 39.10 33.84 70	49.30 41.34 35.88 50	50.95 43.99 38.13 57	57.17 46.96 38.98 48	55.38 47.98 42.03 57

          First in thread      Previous in thread

Copyright and Legal Notices

All Rights Reserved.