Geodesic
Weakly and Strongly Polynomial Algorithms for Computing the Maximum Decrease in Uniform Arc Capacities
Yugoslav journal of operations research, Tome 26 (2016) no. 2, p. 159

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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 $\tau > 0$, the network $D$ with arc capacities $U - \tau$ is called the $\tau$-network. The goal of the problem is to compute the largest $\tau$ such that the $\tau$-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(m^2n)$ time approach is presented, where $m$ is the number of arcs. Both weakly and strongly polynomial algorithms are inspired by McCormick and Ervolina(1994).
Classification : 90B18
Keywords: Optimal Witness, Feasible Flow, Maximum Flow. 
@article{YJOR_2016_26_2_a1,
     author = {Mehdi Ghiyasvand},
     title = {Weakly and {Strongly} {Polynomial} {Algorithms} for {Computing} the {Maximum} {Decrease} in {Uniform} {Arc} {Capacities}},
     journal = {Yugoslav journal of operations research},
     pages = {159 },
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2016_26_2_a1/}
}
TY  - JOUR
AU  - Mehdi Ghiyasvand
TI  - Weakly and Strongly Polynomial Algorithms for Computing the Maximum Decrease in Uniform Arc Capacities
JO  - Yugoslav journal of operations research
PY  - 2016
SP  - 159 
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2016_26_2_a1/
LA  - en
ID  - YJOR_2016_26_2_a1
ER  - 
%0 Journal Article
%A Mehdi Ghiyasvand
%T Weakly and Strongly Polynomial Algorithms for Computing the Maximum Decrease in Uniform Arc Capacities
%J Yugoslav journal of operations research
%D 2016
%P 159 
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2016_26_2_a1/
%G en
%F YJOR_2016_26_2_a1
Mehdi Ghiyasvand. Weakly and Strongly Polynomial Algorithms for Computing the Maximum Decrease in Uniform Arc Capacities. Yugoslav journal of operations research, Tome 26 (2016) no. 2, p. 159 . http://geodesic.mathdoc.fr/item/YJOR_2016_26_2_a1/