نوع مقاله : علمی-پژوهشی
نویسندگان
1 آزمایشگاه تحقیق و توسعه نرم‌افزار- دانشکده مهندسی کامپیوتر- دانشگاه تربیت دبیر شهید رجایی
2 آزمایشگاه تحقیق و توسعه نرم‌افزار- گروه نرم‌افزار- دانشکده مهندسی کامپیوتر- دانشگاه تربیت دبیر شهید رجایی
چکیده
کلیدواژه‌ها
عنوان مقاله [English]
نویسندگان [English]
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.
کلیدواژه‌ها [English]
)