A transitive closure algorithm |
| |
| Authors: | Paul Purdom Jr |
| |
| Institution: | (1) Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, USA |
| |
| Abstract: | An algorithm is given for computing the transitive closure of a directed graph in a time no greater thana
1
N
1
n+a
2
n
2 for largen wherea
1 anda
2 are constants depending on the computer used to execute the algorithm,n is the number of nodes in the graph andN
1 is the number of arcs (not counting those arcs which are part of a cycle and not counting those arcs which can be removed without changing the transitive closure). For graphs where each arc is selected at random with probabilityp, the average time to compute the transitive closure is no greater than min{a
1
pn
3+a
2
n
2, 1/2a
1
n
2
p
–2+a
2
n
2} for largen. The algorithm will compute the transitive closure of an undirected graph in a time no greater thana
2
n
2 for largen. The method uses aboutn
2+n bits and 5n words of storage (where each word can holdn+2 values). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
