رویکرد مبتنی بر مسیر برای شناسایی ریوس بحرانی در گراف

در این مقاله، مساله شناسایی ریوس بحرانی در گراف با شاخص مبتنی بر فاصله بررسی می گردد که در آن، باید زیرمجموعه ای از ریوس گراف حذف شوند به طوری که میزان همبندی در گراف باقیمانده کمینه گردد. برای سنجش میزان همبندی، طول کوتاهترین مسیر میان هر جفت از ریوس، ملاک عمل قرار می گیرد و هرچه این طول بیشتر باشد به مفهوم از هم گسیختگی بیشتر شبکه باقیمانده است. در ادبیات، یک مدل برنامه ریزی عددصحیح و نیز روشی دقیق برای حل این مساله ارایه شده است، اما زمان محاسباتی هر دو رویکرد، وقتی قطر گراف بزرگ و طول کمانها با یکدیگر متفاوت باشند، بسیار بالاست. برای بهبود ضعف مذکور، در این مقاله یک فرمول بندی جدید برای مساله ارایه می کنیم که مبتنی بر شناسایی همه مسیرهای موجود در گراف است. نتایج محاسباتی مزیت رویکرد پیشنهادی را نسبت به روش های قبلی روی گرافهایی با چگالی پایین، تصدیق می کنند.

کلیدواژه ها:

شناسایی ریوس بحرانی ، مدل دوسطحی ، مدل مبتنی بر مسیر ، الگوریتم شناسایی همه مسیرها