سال انتشار: ۱۳۹۰

محل انتشار: نوزدهمین کنفرانس مهندسی برق ایران

تعداد صفحات: ۶

نویسنده(ها):

فاطمه کشاورزکوهجردی – دانشگاه آزاد اسلامی واحد تهران شمال
علیرضا باقری – دانشگاه صنعتی امیرکبیر
بهروز طایفه رضایی – پژوهشکده ریاضیات و فیزیک نظری

چکیده:

گراف شبکهای، زیر گرافی متناهی از گراف شبکهای صحیح نامتناهی G¥ است. گراف شبکهای با مرز خارجی مستطیلی گراف شبکه مستطیلی نامیده میشود. برای گرافهای عمومی، مسأله طولانیترین مسیر یکی از مسایلNP-hard مشهور است و تاکنون تنها برای تعداد بسیار اندکی از کلاس گرافها به صورت چند جملهای حل شده است. در این مقاله الگوریتمی کارا برای یافتن طولانیترین مسیرها بین هر دو رأس معین در گراف شبکه مستطیلی ارائه میدهیم