We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
WEAKLY AND STRONGLY POLYNOMIAL ALGORITHMS FOR COMPUTING THE MAXIMUM DECREASE IN UNIFORM ARC CAPACITIES.
- Authors
GHIYASVAND, Mehdi
- Abstract
In this paper, a new problem on a directed network is presented. Let D be a feasible network such that all arc capacities are equal to U. Given a T > 0, the network D with arc capacities U - T is called the R-network. The goal of the problem is to compute the largest T such that the r-network is feasible. First, we present a weakly polynomial time algorithm to solve this problem, which runs in 0(log(«L/)) maximum flow computations, where n is the number of nodes. Then, an 0{m2n) time approach is presented, where m is the number of arcs. Both weakly and strongly polynomial algorithms are inspired by McCormick and Ervolina(1994).
- Subjects
POLYNOMIAL approximation; ALGORITHMS; FEASIBILITY studies
- Publication
Yugoslav Journal of Operations Research, 2016, Vol 26, Issue 2, p159
- ISSN
0354-0243
- Publication type
Article
- DOI
10.2298/YJOR141217015G