کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1705936 1012445 2011 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An O(mn log (nU)) time algorithm to solve the feasibility problem
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مکانیک محاسباتی
پیش نمایش صفحه اول مقاله
An O(mn log (nU)) time algorithm to solve the feasibility problem
چکیده انگلیسی

The phase I maximum flow and most positive cut methods are used to solve the feasibility problem. Both of these methods take one maximum flow computation. Thus the feasibility problem can be solved using maximum flow algorithms. Let n and m be the number of nodes and arcs, respectively. In this paper, we present an algorithm to solve the feasibility problem with integer lower and upper bounds. The running time of our algorithm is O(mn log (nU)), where U is the value of maximum upper bound. Our algorithm improves the O(m2 log (nU))-time algorithm in [12]. Hence the current algorithm improves the running time in [12] by a factor of n. Sleator and Goldberg’s algorithm is one of the well-known maximum flow algorithms, which runs in O(mn log n) time, see [5]. Under similarity assumption [11], our algorithm runs in O(mn log n) time, which is the running time of Sleator and Goldberg’s algorithm. The merit of our algorithm is that, in the case of infeasibility of the given network, it not only diagnoses infeasibility but also presents some information that is useful to modeler in estimating the maximum cost of adjusting the infeasible network.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematical Modelling - Volume 35, Issue 11, November 2011, Pages 5276–5285
نویسندگان
,