تعمیم الگوریتم مقیاس بندی ظرفیت دو مرحله ای

در این مقاله، یکی از الگوریتم های کارا برای حل مسیله ماکزیمم جریان را تعمیم می دهیم . الگوریتم مقیاس بندی ظرفیت دو مرحله ای با پارامتر مقیاس 2 و پیچیدگی زمانی آن ( mm log) () است . در این مقاله به بررسی حالت کلی پارامتر مقیاس ، اول ، در این الگوریتم پرداخته و الگوریتم مقیاس بندی ظرفیت دو مرحله ای با پارامتر مقیاس اول ، را ارایه می دهیم و نشان می دهیم به ازاء مقادیر 2حال پیچیدگی الگوریتم برابر ( را با O (nm log خواهد بود. به علاوه چنان چه در مسایل ماکزیمم جریان 2 < U / n باشد، با قرار دادن / / f} = U می توان این مسایل را با استفاده از این نسخه جدید از الگوریتم مقیاس بندی در بهترین زمان اجرا برای مسایل ماکزیمم جریان ، (اO(n Ir حل نمود .

کلیدواژه ها:

شبکه جریان ، ماکزیمم جریان ، مقیاس بندی ظرفیت