Weakly and strongly polynomial algorithms for computing the maximum decrease in uniform arc capacities
DOI:
https://doi.org/10.2298/YJOR141217015GKeywords:
optimal witness, feasible flow, maximum flowAbstract
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 t-network. The goal of the problem is to compute the largest t such that the t-network is feasible. First, we present a weakly polynomial time algorithm to solve this problem, which runs in O(log(nU)) maximum flow computations, where n is the number of nodes. Then, an O(m2n) time approach is presented, where m is the number of arcs. Both the weakly and strongly polynomial algorithms are inspired by McCormick and Ervolina (1994).References
Ahuja, R.K., Magnanti, T.L., and Orlin, J.B., Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs, NJ, 1993.
Aneja, Y.P., Chandrasekaran, R., and Nair, K.P.K., “Maximizing residual flow under an arc destruction”, Networks, 38 (2001) 194-198.
Ball, M.O., Golden, B.L., and Vohra, R.V., “Finding the most vital arcs in a network”, Operations Research Letters, 8 (1989) 73-76.
Bar-Noy, A., Khuller, S., and Schieber, B., “The complexity of finding most vital arcs and nodes”, TRCS-TR-3539, Institute for Advanced Studies, University of Maryland, College Park, MD, 1995.
Barton, A.J., “Addressing the problem of finding a single vital edge in a maximum flow graph”, NRCERB-1129, 2005.
Corley, H.W., and Sha, D.Y., “Most vital links and nodes in weighted networks”, Operations Research Letters, 1 (1982) 157-160.
Hoffman, A.J., “Some recent applications of the theory of linear inequalities to extremal combinatorial analysis”, American Mathematical Society, 10 (1960) 113-127.
Ivanchev, D., “Finding the k most vital elements of an s-t planar directed network”, Yugoslav Journal of Operations Research, 10 (2000) 13-26.
Malik, K., Mittal, A.K., and Gupta, S.K., “The K most vital arcs in the shortest path problem”, Operations Research Letters, 8 (1989) 223-227.
McCormick, S.T., and Ervolina, T.R., “Computing Maximum Mean Cuts”, Discrete Applied Math, 52 (1994) 53-70.
Nardelli, E., Proietti, G., and Widmayer, P., “Finding the detour-critical edge of a shortest path between two nodes”, Information Processing Letters, 67 (1998) 51-54.
Nardelli, E., Proietti, G., and Widmayer, P., “A faster computation of the most vital edge of a shortest path between two nodes”, Information Processing Letters, 79 (2001) 81-85.
Nardelli, E., Proietti, G., and Widmayer, P., “Finding the most vital node of a shortest path”, Theoretical Computer Science, 296 (2003) 167-177.
Orlin, J.B., “Max flows in O(mn) time, or better”, STOC (2013) 765-774.
Ratliff, D., Sicilia, T., and Lubore, H., “Finding the n most vital links in flow networks”, Management Science, 21 (1975) 531-539.
Downloads
Published
Issue
Section
License
Copyright (c) 2016 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
