Academic
Publications
Locating Sources to Meet Flow Demands in Undirected Networks

Locating Sources to Meet Flow Demands in Undirected Networks,10.1006/jagm.2001.1203,Journal of Algorithms,Kouji Arata,Satoru Iwata,Kazuhisa Makino,Sat

Locating Sources to Meet Flow Demands in Undirected Networks   (Citations: 28)
BibTex | RIS | RefWorks Download
This paper deals with the problem of finding a minimum-cost vertex subset S in an undirected network such that for each vertex v we can send d(v) units of flow from S to v. Although this problem is NP-hard in general, H. Tamura, H. Sugawara, M. Sengoku, and S. Shinoda (IEICE Trans. Fund. J81-A (1998), 863–869) have presented a greedy algorithm for solving the special case with uniform costs on the vertices. We give a simpler proof on the validity of the greedy algorithm using linear programming duality and improve the running time bound from O(n2M(n,m)) to O(nM(n,m)), where n is the number of vertices in the network and M(n,m) denotes the time for max-flow computation in a network with n vertices and m edges. We also present an O(n(m+n logn)) time algorithm for the special case with uniform demands and arbitrary costs.
Journal: Journal of Algorithms - JAL , vol. 42, no. 1, pp. 54-68, 2002
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: