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 50
- Downloads 0
Optimization Techniques for Fuzzy-PID Control of CSC-Based D-STATCOM for Power Quality Improvement
This study focuses on enhancing power quality using a Current Source Converter (CSC) based Dynamic Voltage Restorer (D-STATCOM) controlled by a Fuzzy Logic-PID (Fuzzy-PID) controller. Power quality improvement is a vital...
CUMULATIVE SUM, CUMULATIVE SCORE AND NONPARAMETRIC CUSUM CONTROL CHARTS FOR DETECTING MEAN/MEDIAN CHANGE
Various control charts are already developed for the problem of detecting any shift in the mean/median of a sequence of observations from a specified control value taken from some process. Some of them for detecting smal...
Deep Learning-Based Lung Medical Image Recognition
Pulmonary nodules serve as critical indicators for early lung cancer diagnosis, making their detection and classification essential. The prevalent use of transfer learning in recognition algorithms often encounters a sig...
Enhanced Churn Prediction in the Telecommunication Industry
Prediction models are usually built by applying a supervised learning algorithm to historical data. This involves the use of data analytics system that uses real-time integration and dynamic real time responses data to d...
Risk Management in Infrastructure Projects
Management of risks in the infrastructure projects has been categorized of utmost importance to the process of management so that the project objectives and motives in terms of time, cost, quality may be accomplished. Th...