International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Since Year 2012 | Open Access | Double Blind Reviewed

ISSN: 2319-7064




Downloads: 0

Research Paper | Computer and Mathematical Sciences | India | Volume 10 Issue 6, June 2021


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

Abhijit Tripathy


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


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


Edition: Volume 10 Issue 6, June 2021,


Pages: 869 - 873


How to Cite this Article?

Abhijit Tripathy, "Transitive Closure of a Graph using Graph Powering & Further Optimization by Euler's Fast Powering Algorithm", International Journal of Science and Research (IJSR), Volume 10 Issue 6, June 2021, pp. 869-873, https://www.ijsr.net/get_abstract.php?paper_id=MR21613054013

How to Share this Article?

Enter Your Email Address




Similar Articles with Keyword 'graph'

Downloads: 0

Research Paper, Computer and Mathematical Sciences, Philippines, Volume 10 Issue 5, May 2021

Pages: 772 - 774

Symbolic Regression via Genetic Programming; Philippines Population Prediction: 2010-2020

Teotima Evangelista Gorres - Abato [2]

Share this Article

Downloads: 7 | Monthly Hits: ⮙1

Research Paper, Computer and Mathematical Sciences, Philippines, Volume 10 Issue 5, May 2021

Pages: 769 - 771

Symbolic Regression with Genetic Programming in Forecasting Population Growth of the Philippines

Teotima Evangelista Gorres - Abato [2]

Share this Article


Top