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(nalgorithm which is used in most books on algorithms. ^{3}) The time complexity of my algorithm is O(N It was found out that the total time taken to calculate the transitive closure in a single source graph is proportional to b 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 b Journal paper being sent for review by TALG, ACM. Please contact me for explanation of this algorithm. |