An algorithm for source location in directed graphs

Mihály Bárász, Johanna Becker, András Frank

Published in:
Operations Research Letters. 33 (2005) 221-230.


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2004},
NUMBER = {TR-2004-06}

Last modification: 29.12.2020. Please email your comments to Tamás Király!