مشاهده مشخصات مقاله
الگوریتمی ابتکاری جهت مسأله تشخیص یکریختی گراف‌ها مبتنی بر دوری از مرکز گراف
|
Authors |
|
|
Conference |
بیست و پنجمین کنفرانس بین‌المللی انجمن کامپیوتر ایران |
|
Abstract |
مسأله یکریختی گراف‌ها از مجموعه مسائل باز از لحاظ پیچیدگی محاسباتی است که فقط تعلق آن به کلاس NP مشخص است ولی تعلق آن به P یا NP-Complete مشخص نیست. راه‌حل مسأله در زمان چندجمله‌ای هنوز ناشناخته است و لذا زمینه برای تحقیق و ایده‌پردازی فراهم می‌باشد. از این رو الگوریتم‌های چندجمله‌ای برای این مسأله جزو الگوریتم‌های ابتکاری محسوب می‌شوند. این مقاله به بررسی راه‌های تعیین یکریختی دو گراف متناهی با یکدیگر و ارائه یک روش ابتکاری جدید می‌پردازد. الگوریتمی پیشنهاد می‌شود که گراف ورودی را به یک رشته‌کد پرانتزی تبدیل می‌کند و سپس به جای مقایسه دو گراف رشته کدهای آن دو گراف با هم مقایسه می‌شوند و یکریختی یا عدم یکریختی میان آن‌ها تشخیص داده می‌شود. زمان اجرای این الگوریتم O(ne) است و در دسته الگوریتم‌های "برچسب‌گذاری کانونی " برای گراف‌های "همبند و بدون برچسب " قرار دارد. بعد از پیاده¬سازی این الگوریتم و بررسی نتایج آن مشخص شد که با عملکرد صحیح بیشتر از 99%، عدم یکریختی میان گراف‌های غیریکریخت به درستی تشخیص داده می‌شود. |
|
قیمت |
-
برای اعضای سایت : 100,000 Rial
-
برای دانشجویان عضو انجمن : 20,000 Rial
-
برای اعضای عادی انجمن : 40,000 Rial
|
خرید مقاله
|
|
.gif){kind=icon}