الگوریتمی کارا برای یافتن طولانیترین مسیر در گراف شبکه مستطیلی

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

کلیدواژه ها:

الگوریتم ترتیبی ، گراف شبکه ، (Grid Graphگراف شبکه مستطیلیRectangular Grid Graph)طولانیترین مسیر .(Longest Path