Design of a Ripple Type algorithm to find Transitive Closure in graphs

posted Dec 21, 2010, 11:21 PM by Unknown user   [ updated Feb 25, 2012, 12:01 AM by Unknown user ]

Designed an algorithm to find the transitive closure in graphs. The algorithm has a unique property where time complexity is inversely proportional to the average branching factor of a graph. In fact it challenges the optimality of Warshall's O(n3) algorithm which is used in most books on algorithms. 

The time complexity of my algorithm is O(N3/E3). Where N is the number of nodes and E is the number of edges. The developed algorithm was initially hypothesized using flow charts and then it was tested by formally proving the hypothesis using running code. The input test case was varied from 10 to 500 nodes and at max n2 edges (i.e. 100 to 250,000 edges). The branching factor varied from 2 to 143 in these randomly generated graphs


It was found out that the total time taken to calculate the transitive closure in a single source graph is proportional to b-3 (branching factor = Total-Edges/Total-Nodes). A graph of the result is provided below. 


The graph below shows the big-oh complexity (upper limit) and theeta complexity (lower limit) of the algorithm. 



The graph below shows the variation of total-time and the branching factor of a graph. 



The graph below shows the variation of the b3 with total-time. 



Journal paper being sent for review by TALG, ACM. 

Please contact me for explanation of this algorithm. 


Comments