Reducing Complexity of Graph Isomorphism Problem
Journal Title: International Journal of Innovative Research in Computer Science and Technology - Year 2020, Vol 8, Issue 3
Abstract
Graph isomorphism has been discussed in the literature as NP-hard problem. It has applications in various areas. Work done earlier in this area employs backtracking for identifying isomorphism between given two graphs as a result with the increase in size of the graph the time to solve the problem becomes exponential. The proposed work presents a polynomial time algorithm (PTGI) which tries to solve graph isomorphism between given two directed graphs. Some distinguishing features associated with each vertex are stored. These features are exploited in dividing the vertices of the graph into equivalence classes from which canonical representation of the graph is generated. Comparing these features of the vertices of the given two graphs solves isomorphism in polynomial time.
Authors and Affiliations
Shalini Bhaskar Bajaj
Keywords
Related Articles
- EP ID EP747810
- DOI 10.21276/ijircst.2020.8.3.15
- Views 2
- Downloads 0
An Overview on Green Technologies
Climate change, energy depletion, global warming, as well as other worries about the environment have prompted the development of green technology in recent years. According to researchers, as the degree of sustainable d...
Air Quality in India: A Review Paper
Delhi, India's state capital, has a reputation for being one of the world's most densely populated cities. As a consequence of their findings in 2014, the World Health Organization (WHO) released this. 2014, Bandyopadhya...
Novel Method of Speed Control of 3 Phase Induction Motor by Chopper Circuit
Power electronics advancements in recent years have had a significant influence on the functioning induction machine drives, as well as speed control My work provides a novel stinger approach for managing the pitch of a...
Estimate US Restaurant Firm Failure: The Artificial Neural System Model Versus Logistic Regression Model
In view of recent years' financial information of US restaurant firms, this investigation created disappointment forecast models utilizing strategic relapse and artificial neural systems (ANNs). The discoveries demonstra...
Barcode Recognition Techniques: Review & Application
Because of the importance of maintaining track of all products in one location, barcodes have become important elements of sales and product services. Many methods have been developed to make the task of reading barcodes...