آمار
| تعداد نشریات | 43 |
| تعداد شماره‌ها | 1,275 |
| تعداد مقالات | 15,744 |
| تعداد مشاهده مقاله | 51,862,662 |
| تعداد دریافت فایل اصل مقاله | 14,688,192 |
An Improved Heuristic Algorithm for the Graph Isomorphism Problem | ||
| مجله مهندسی برق دانشگاه تبریز | ||
| مقالات آماده انتشار، اصلاح شده برای چاپ، انتشار آنلاین از تاریخ 09 مهر 1403 | ||
| نوع مقاله: علمی-پژوهشی | ||
| شناسه دیجیتال (DOI): 10.22034/tjee.2024.57285.4657 | ||
| نویسندگان | ||
| سمیه چک1؛ علی نوراله* 2 | ||
| 1آزمایشگاه تحقیق و توسعه نرم‌افزار- دانشکده مهندسی کامپیوتر- دانشگاه تربیت دبیر شهید رجایی | ||
| 2آزمایشگاه تحقیق و توسعه نرم‌افزار- گروه نرم‌افزار- دانشکده مهندسی کامپیوتر- دانشگاه تربیت دبیر شهید رجایی | ||
| چکیده | ||
| 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 | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 15 |
||