دانشگاه صنعتی امیرکبیر، دانشکده ریافسی و علوم کامپیوتر بررسی مساله ی می نیمم جریان محدود شده

مساله ی می نیمم جریان محدود شده در یک شبکه جریان عبارت است از یافتن جریانی که ز یک گره به عنوان منبع به گره دیگر به عنوان مقصد ارسال شود به طوریکه مقدار جریان می نیمم بوده و سود ارسال آن کمتر از مقدار ثابت (ا نباشد. در این مقاله برای حل این مساله، الگوریتمی با مرتبه زمانی ((O (DS (In/m 0/ C از نوع الگوریتم های طولانی ترین مسیر متوالی ارایه می گردد که در آن 171 و 1 / به ترتیب تعداد کمان ها و تعداد گره ها درشبکه بوده و C ماکزیمم سود به ازای کلیه کمان ها و (ITC و S (Il ml زمان لازم برای حل طولانی ترین مسیر می باشد.

کلیدواژه ها:

می نیمم جریان ، ماکزیمم جریان ، طولانی ترین مسیر