An Improved Heuristic Algorithm for the Graph Isomorphism Problem

Document Type : Original Article

Authors

Software Systems Research and Development Laboratory / Faculty of Computer Engineering, Shahid Rajaee Teacher Training University

Abstract

The Graph Isomorphism Problem (GIP) is an open problem because of its computational complexity. No polynomial-time deterministic algorithm has been proposed yet, and heuristic and meta-heuristic approaches have been the only ways to solve it. Because its belonging to the NP-complete problem has not yet been proven, it is considered an NP problem. This paper introduces a simple but efficient polynomial algorithm, both in terms of computational complexity and memory complexity, to determine the isomorphism of connected unlabeled graphs. The proposed algorithm introduces two functions that compute the features for all vertices and edges. The outputs of the function provide canonical labeling to the given graphs, and a comparison of these labels specifies the graph isomorphism of the given graphs. The experimental results show that the proposed algorithm correctly detects the isomorphism of the graphs in more than 99% of cases. The algorithm requires Ο(n^3) time where n is the number of vertices of the given graphs.

Keywords

TABRIZ JOURNAL OF ELECTRICAL ENGINEERING

Articles in Press, Corrected Proof
Available Online from 30 September 2024

Files

Share

How to cite

Statistics