الگوریتمی برای حل مسأله جریان ماکسیمم مقید

مسأله جریان ماکسیمم مقید یک نسخه خاصی از مسأله جریان ماکسیمم کلاسیک است که در آن حداکثرجریان ممکن از گره منبع به گره مقصد در یک شبکه جهتدار ظرفی تدار با هزین ههای یالی که هزینه کل انتقال جریان باید در محدوده بودجه قرار گیرد فرستاده می شود.مطالعه مسأله جریان ماکسیمم مقید مهم است چون دارای کاربردهای فراوان از جمله در تدارکات، مخابرات و شبکه های کامپیوتری و همچنین بانسخه هایی از مسأله کلاسیک مانند مسأله کوتاه ترین مسیر مقید، مسأله حمل و نقل مقید و مسأله تخصیص مقید در ارتباط است که همه آنها دارای کابردهای فراوان خوبی هستند. در این مقاله هدف بررسی الگوریتم مقیاس بندی دوگانه برای حل مسأله جریان ماکسیمم مقید است که دارای پیچیدگی زمانی O(n2mlogmlog(nc) log U) میباشد.

کلیدواژه ها:

جریانهای شبکه ، جریان ماکسیمم ، جریان شبکه باکمترین هزینه ، مقیاسبندی ، پیچیدگی محاسباتی