|
Published in:
Ito, Makino, Arata, Honami, Itatsu, and Fujishige \cite{IMAIF} provided a theoretical answer to a source location problem by proving that the minimum cardinality of a subset R of nodes in an edge-capacitated directed graph D=(V,A) so that the maximum flow-amount from R to every node v\in V-R is at least k and the maximum flow amount from every node v \in V-R to R is at least l is equal to the maximum number of pairwise disjoint deficient sets where a subset of nodes is deficient if its in-capacity is less than k or its out-capacity is less than l. They also showed how this theorem gave rise to a polynomial time algorithm to compute the optima in question in case the demands k and l are fixed, and posed as an open problem of developing an algorithm that is (strongly) polynomial not only in the size of the digraph but in k and l, as well. The present work describes such an algorithm.
Bibtex entry:
| AUTHOR | = | {B{\'a}r{\'a}sz, Mih{\'a}ly and Becker, Johanna and Frank, Andr{\'a}s}, |
| TITLE | = | {An algorithm for source location in directed graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2004}, |
| NUMBER | = | {TR-2004-06} |