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/