
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Faster and Flexible Algorithm for a Location Problem on Undirected Flow Networks
Hiro ITO Hideyuki UEHARA Mitsuo YOKOYAMA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E83A
No.4
pp.704712 Publication Date: 2000/04/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: graph, network flow, location problem, node subset, polynomial time, algorithm,
Full Text: PDF(558.8KB)>>
Summary:
For a given graph G=(V, E), edge capacities c(e) for edges e E, and flowdemands d(v) for nodes v V, a problem of finding the minimum size sourceset S V such that the maximum flowamount 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.

