L E D A Static Graphs

Running Times for L E D A Maxflow Algorithms


The experiments (running times in seconds) were made using a Sun UltraSPARC IIi 440 Mhz with 256 MBytes running Solaris 2.7 with gcc-3.0.3.

An ak(i)-network consists of 4i + 6 nodes and 6i + 7 edges. For a network of n nodes and m edges, the space requirement is 12n + 11m words for the L E D A graph, 5n + 5m words for the static bidirectional graph, and 5n +4m words for the static opposite graph. For an ak(40.000)-network the L E D A graph uses 17.396 MBytes, the static bidirectional graph 7.630 MBytes and the static opposite graph 6.714 MBytes. We also tested several graph implementations of other packages but did not find a single one beating the running time of our static graph.

Generator: ak(n)
5.000
10.000
15.000
20.000
25.000
30.000
35.000
40.000

external arrays  
L E D A Graph
7.57
31.58
72.50
130.40
236.44
304.93
464.06
591.17
static bidirectional graph
7.46
30.18
67.09
122.65
191.80
281.91
378.39
525.70
static opposite graph
6.76
27.14
60.69
110.99
174.58
256.99
350.43
454.64

dynamic slot assignment                
L E D A Graph
6.42
27.14
70.93
134.70
184.67
291.40
475.26
580.04
static bidirectional graph
5.66
22.58
51.27
107.10
149.26
204.99
284.35
427.77
static opposite graph
5.35
21.17
50.01
90.01
143.92
204.21
275.38
364.50

static slot assignment                
L E D A Graph
3.66
15.38
48.16
94.75
117.38
205.68
382.37
435.24
static bidirectional graph
2.29
9.28
21.28
48.94
58.35
85.38
118.00
196.80
static opposite graph
2.30
9.30
22.12
38.49
67.05
85.39
113.06
150.64

 

 


Help   Legal     Copyright 2004 Algorithmic Solutions Software GmbH