رویکرد مبتنی بر مسیر برای شناسایی ریوس بحرانی در گراف
Publish place: 14th International Industrial Engineering Conference
Publish Year: 1396
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 345
This Paper With 10 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
IIEC14_134
تاریخ نمایه سازی: 26 مرداد 1397
Abstract:
در این مقاله، مساله شناسایی ریوس بحرانی در گراف با شاخص مبتنی بر فاصله بررسی می گردد که در آن، باید زیرمجموعه ای از ریوس گراف حذف شوند به طوری که میزان همبندی در گراف باقیمانده کمینه گردد. برای سنجش میزان همبندی، طول کوتاهترین مسیر میان هر جفت از ریوس، ملاک عمل قرار می گیرد و هرچه این طول بیشتر باشد به مفهوم از هم گسیختگی بیشتر شبکه باقیمانده است. در ادبیات، یک مدل برنامه ریزی عددصحیح و نیز روشی دقیق برای حل این مساله ارایه شده است، اما زمان محاسباتی هر دو رویکرد، وقتی قطر گراف بزرگ و طول کمانها با یکدیگر متفاوت باشند، بسیار بالاست. برای بهبود ضعف مذکور، در این مقاله یک فرمول بندی جدید برای مساله ارایه می کنیم که مبتنی بر شناسایی همه مسیرهای موجود در گراف است. نتایج محاسباتی مزیت رویکرد پیشنهادی را نسبت به روش های قبلی روی گرافهایی با چگالی پایین، تصدیق می کنند.
Keywords:
Authors
فاطمه میرعرب رضی
دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر (پلی تکنیک تهران)
فرناز هوشمندخلیق
دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر (پلی تکنیک تهران)
سیدعلی میرحسنی
دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر (پلی تکنیک تهران)