الگوریتمی مکاشفه ای جهت مساله تشخیص یکریختی گراف ها مبتنی بر قطر

سال انتشار: 1398
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 1,572

فایل این مقاله در 12 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

CEPS06_076

تاریخ نمایه سازی: 9 اردیبهشت 1399

چکیده مقاله:

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

نویسندگان

سمیه چک

دانشجوی کارشناسی ارشد، آزمایشگاه تحقیق و توسعه نرم افزار، دانشگاه تربیت دبیر شهید رجایی ، تهران

علی نوراله

استادیار، دانشکده مهندسی کامپیوتر، آزمایشگاه تحقیق و توسعه نرمافزار، دانشگاه تربیت دبیر شهید رجایی ، تهران