ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Transitive Closure of a Graph using Graph Powering & Further Optimization by Euler's Fast Powering Algorithm

Journal: International Journal of Science and Research (IJSR) (Vol.10, No. 6)

Publication Date:

Authors : ;

Page : 869-873

Keywords : graph algorithms; transitive closure; graph powering; discrete mathematics; Euler's fast powering;

Source : Downloadexternal Find it from : Google Scholarexternal

Abstract

A graph is a collection of nodes and edges. Transitive closure matrix is a matrix formed by the reach-ability factor, which means if one node A of the graph is reachable from another node B, then there exists a positive reach-ability between A and B, negative reach-ability otherwise. This can be easily denoted by using binary denotation of 0 and 1. Graph powering is a technique in discrete mathematics and graph theory where our concern is to get the path between the nodes of a graph by using the powering principle. In simple words, if we take the rth power of any given graph G then that will give us another graph G(r) which has exactly the same vertices, but the number of edges will change. In the powered graph G(r) there will be a connection between any two nodes if there exits a path which has a length less than r between them. This small intuition can help us in finding the transitive closure of a graph in O(V^4) time complexity and O(V^2) space complexity. We can improve the time complexity of the above mentioned algorithm by using Euler's Fast Powering Algorithm to O(V^3 logV).

Last modified: 2021-07-05 13:46:22