A Generalization of Two-phase Capacity Scaling Algorithm
Publish place: 2nd International Conference on Management, Entrepreneurship and Economic Development
Publish Year: 1392
نوع سند: مقاله کنفرانسی
زبان: English
View: 849
This Paper With 10 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
EME02_1730
تاریخ نمایه سازی: 14 شهریور 1393
Abstract:
In this paper, we generalize the two-phase capacity scaling algorithm in the design of algorithms for the maximum flow problems. The two-phase capacity algorithm uses a factor of value 2 and runs in O(nm log U/n).We consider the general case of scaling factor β. It will be shown that for β≥2 ,the general two-phase capacity scaling algorithm runs in . Furthermore, in the maximum flow problems with U/n ,if we let ,these problems can be solved by using new variant of scaling algorithm in O(nm) time
Keywords:
Authors
Razieh Shamsi
Minab Branch, Islamic Azad University, Minab, Iran
Fatemeh haghshenas
Department of Mathematics, Payame Noor University, I.R. of IRAN