Copy
Hiro ITO, Hideyuki UEHARA, Mitsuo YOKOYAMA, "A Faster and Flexible Algorithm for a Location Problem on Undirected Flow Networks" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 4, pp. 704-712, April 2000, doi: .
Abstract: For a given graph G=(V, E), edge capacities c(e) for edges e E, and flow-demands d(v) for nodes v V, a problem of finding the minimum size source-set S V such that the maximum flow-amount between S and v is greater than or equal to d(v) for every v V is called generalized plural cover problem (GPC). For this problem, O(np s(n,m)) time algorithm is presented, where n, m, and p is the number of nodes, edges, and different values of d(v), respectively, and s(n,m) is the time required to solve the maximum flow problem of a graph with n nodes and m edges. This algorithm also constructs a set of optimal solutions in the same time. This property is convenient for applying it to real problems, because other constraints can also be taken into account.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_4_704/_p
Copy
@ARTICLE{e83-a_4_704,
author={Hiro ITO, Hideyuki UEHARA, Mitsuo YOKOYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Faster and Flexible Algorithm for a Location Problem on Undirected Flow Networks},
year={2000},
volume={E83-A},
number={4},
pages={704-712},
abstract={For a given graph G=(V, E), edge capacities c(e) for edges e E, and flow-demands d(v) for nodes v V, a problem of finding the minimum size source-set S V such that the maximum flow-amount between S and v is greater than or equal to d(v) for every v V is called generalized plural cover problem (GPC). For this problem, O(np s(n,m)) time algorithm is presented, where n, m, and p is the number of nodes, edges, and different values of d(v), respectively, and s(n,m) is the time required to solve the maximum flow problem of a graph with n nodes and m edges. This algorithm also constructs a set of optimal solutions in the same time. This property is convenient for applying it to real problems, because other constraints can also be taken into account.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - A Faster and Flexible Algorithm for a Location Problem on Undirected Flow Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 704
EP - 712
AU - Hiro ITO
AU - Hideyuki UEHARA
AU - Mitsuo YOKOYAMA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2000
AB - For a given graph G=(V, E), edge capacities c(e) for edges e E, and flow-demands d(v) for nodes v V, a problem of finding the minimum size source-set S V such that the maximum flow-amount between S and v is greater than or equal to d(v) for every v V is called generalized plural cover problem (GPC). For this problem, O(np s(n,m)) time algorithm is presented, where n, m, and p is the number of nodes, edges, and different values of d(v), respectively, and s(n,m) is the time required to solve the maximum flow problem of a graph with n nodes and m edges. This algorithm also constructs a set of optimal solutions in the same time. This property is convenient for applying it to real problems, because other constraints can also be taken into account.
ER -