An Improved Heuristic Algorithm for the Graph Isomorphism Problem

Message:
Article Type:
Research/Original Article (دارای رتبه معتبر)
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.

Language:
Persian
Published:
Journal of Electrical Engineering, Volume:55 Issue: 1, Spring 2025
Pages:
19 to 26
https://www.magiran.com/p2864491  
سامانه نویسندگان
  • Corresponding Author (2)
    Ali Nourollah
    Assistant Professor computer engineering, Shahid Rajaee Teacher Training University, Tehran, Iran
    Nourollah، Ali
اطلاعات نویسنده(گان) توسط ایشان ثبت و تکمیل شده‌است. برای مشاهده مشخصات و فهرست همه مطالب، صفحه رزومه را ببینید.