آمار
| تعداد نشریات | 45 |
| تعداد شماره‌ها | 1,381 |
| تعداد مقالات | 16,906 |
| تعداد مشاهده مقاله | 54,424,523 |
| تعداد دریافت فایل اصل مقاله | 17,099,868 |
الگوریتم مکاشفه ای بهبود یافته جهت مساله یکریختی گراف | ||
| مجله مهندسی برق دانشگاه تبریز | ||
| دوره 55، شماره 1 - شماره پیاپی 111، خرداد 1404، صفحه 19-26 اصل مقاله (760.88 K) | ||
| نوع مقاله: علمی-پژوهشی | ||
| شناسه دیجیتال (DOI): 10.22034/tjee.2024.57285.4657 | ||
| نویسندگان | ||
| Somayeh Check1؛ Ali Nourollah* 2 | ||
| 1آزمایشگاه تحقیق و توسعه نرم‌افزار- دانشکده مهندسی کامپیوتر- دانشگاه تربیت دبیر شهید رجایی | ||
| 2آزمایشگاه تحقیق و توسعه نرم‌افزار- گروه نرم‌افزار- دانشکده مهندسی کامپیوتر- دانشگاه تربیت دبیر شهید رجایی | ||
| چکیده | ||
| مساله یکریختی گراف (GIP) از لحاظ پیچیدگی محاسباتی یک مساله باز است. تاکنون هیچ الگوریتم قطعی با زمان اجرای چندجمله‌ای برای حل آن پیشنهاد‌نشده و روش‌های اکتشافی و فرا‌اکتشافی تنها راه‌حل آن بوده‌است. از آنجا که NP-complete بودن این مساله هنوز به اثبات نرسیده لذا این مساله را جز مسائل NP در نظر گرفته‌اند. در این مقاله یک الگوریتم چندجمله‌ای ساده اما کاربردی هم از لحاظ پیچیدگی زمانی و هم از لحاظ پیچیدگی فضا معرفی شده‌است که در زمان چندجمله‌ای، یکریختی میان گراف‌های همبند بدون برچسب را تشخیص می‌دهد. الگوریتم پیشنهادی دو تابع جهت محاسبه‌ی ویژگی‌های تمامی یال‌ها و برگ‌ها ارائه می‌دهد. خروجی این توابع به ازای هر گراف ورودی یک برچسب کانونی است و تشخیص یکریختی میان گراف‌ها با مقایسه میان برچسب‌ها صورت می‌گیرد. نتایج بدست‌آمده نشان می‌دهد که الگوریتم پیشنهادی با صحت بالاتر از 99درصد یکریختی میان گراف‌ها را تشخیص می‌دهد. پیچیدگی زمانی الگوریتم O(n^3 ) می‌باشد که n برابر تعداد راس‌های گراف ورودی است. | ||
| کلیدواژه‌ها | ||
| یکریختی گراف؛ الگوریتم چندجمله‌ای؛ الگوریتم مکاشفه‌ای؛ برچسب‌گذاری کانونی | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 168 تعداد دریافت فایل اصل مقاله: 40 |
||