الگوریتمی مکاشفه ای جهت مساله تشخیص یکریختی گراف ها مبتنی بر قطر
سال انتشار: 1398
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 1,572
فایل این مقاله در 12 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
CEPS06_076
تاریخ نمایه سازی: 9 اردیبهشت 1399
چکیده مقاله:
تشخیص یکریختی گرافها جزو مجموعه مسائل باز از لحاظ پیچیدگی محاسباتی است که تاکنون هیچ الگوریتم چندجملهای برای آن مطرح نشده و روشهای پیشنهادی برای حل آن باید از شیوه های اکتشافی استفاده کنند، ازاینرو تعلق آن به کلاس NP مشخص است ولی تعلق آن به P یا NP-Complete مشخص نیست. در این مقاله یک الگوریتم ساده و در عین حال کارآمد برای تشخیص یکریختی گرافهای بدون برچسب ارائه میشود که با استفاده از روش کدگذاری کانونی، گراف ورودی را به یک رشتهکد پرانتزی تبدیل میکند و سپس با مقایسه رشتهکد ایجاد شده دوگراف، یکریختی یا عدم یکریختی میان آنها را تشخیص میدهد. ویژگیهای الگوریتم پیشنهادی با جزئیات آن مورد تجزیه و تحلیل قرار میگیرد. نتایج آزمایشات انجام شده بر روی گرافهای ساده و همبند نشان میدهد که الگوریتم پیشنهادی با بازده صحیح بیشتر از %99، عدم یکریختی میان گرافهای غیریکریخت را به درستی تشخیص میدهد. زمان اجرای این الگوریتم Ο( . d| E |) میباشد که | E| تعداد یالهای گراف وd اندازه قطر گراف است.
کلیدواژه ها:
نویسندگان
سمیه چک
دانشجوی کارشناسی ارشد، آزمایشگاه تحقیق و توسعه نرم افزار، دانشگاه تربیت دبیر شهید رجایی ، تهران
علی نوراله
استادیار، دانشکده مهندسی کامپیوتر، آزمایشگاه تحقیق و توسعه نرمافزار، دانشگاه تربیت دبیر شهید رجایی ، تهران