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

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

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

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

سمیرا طارمی – دانشکده علومریاضی، دانشگاه شاهد
بهاره بخشایش –
اردشیر دولتی –

چکیده:

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