|
|
|
|
an improved heuristic algorithm for the graph isomorphism problem
|
|
|
|
|
|
|
|
نویسنده
|
check somayeh ,nourollah ali
|
|
منبع
|
مهندسي برق دانشگاه تبريز - 2025 - دوره : 55 - شماره : 1 - صفحه:19 -26
|
|
چکیده
|
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.
|
|
کلیدواژه
|
graph isomorphism ,polynomial-time algorithm ,heuristic algorithm ,canonical labeling
|
|
آدرس
|
shahid rajaee teacher training university, faculty of computer engineering, software systems research and development laboratory, iran, shahid rajaee teacher training university, faculty of computer engineering, software systems research and development laboratory, iran
|
|
پست الکترونیکی
|
nourollah@sru.ac.ir
|
|
|
|
|
|
|
|
|
|
|
|
|
|
an improved heuristic algorithm for the graph isomorphism problem
|
|
|
|
|
Authors
|
check somayeh ,nourollah ali
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|