مسئله طولانی‌ترین مسیر در گراف‌های توری -t شکل با اندازه زوج
|
|
|
|
|
|
|
|
نویسنده
|
فانی قهدریجانی امیر ,کشاورز کوهجردی فاطمه
|
|
منبع
|
علوم رايانشي - 1402 - دوره : 8 - شماره : 1 - صفحه:59 -75
|
|
چکیده
|
مسئله طولانی‌ترین مسیر، یعنی یافتن یک مسیر ساده با بیشترین تعداد راس، یک مسئله ان‌پی سخت با کاربردهای زیاد است. با این حال این مسئله برای برخی از رده‌های گراف، از جمله گراف‌های توری بدون حفره یک مسئله باز است. گراف توری t-شکل، نوع خاصی از گراف توری بدون حفره است. در این مقاله، نشان می‌دهیم که مسئله طولانی‌ترین مسیر در گراف‌های توریt-شکل با اندازه زوج را می‌توان در زمان خطی محاسبه کرد.
|
|
کلیدواژه
|
گراف توری، گراف توری بدون حفره، مسیر همیلتونی، گراف توری t-شکل، طولانی‌ترین مسیر
|
|
آدرس
|
دانشگاه شاهد, گروه علوم کامپیوتر, ایران, دانشگاه شاهد, گروه علوم کامپیوتر, ایران
|
|
پست الکترونیکی
|
f.keshavarz@shahed.ac.ir
|
|
|
|
|
|
|