Portal de Periódicos da CAPES

A transitive closure algorithm

1970; Springer Science+Business Media; Volume: 10; Issue: 1 Linguagem: Inglês

10.1007/bf01940892

1572-9125

Paul W. Purdom,

Algorithms and Data Compression

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).