Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Greedy Algorithm
Location Problem
Linear Program
Subscribe
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
Edit
Locating Sources to Meet Flow Demands in Undirected Networks
(
Citations: 28
)
BibTex

RIS

RefWorks
Download
Kouji Arata
,
Satoru Iwata
,
Kazuhisa Makino
,
Satoru Fujishige
This paper deals with the problem of finding a minimumcost 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 NPhard in general, H. Tamura, H. Sugawara, M. Sengoku, and S. Shinoda (IEICE Trans. Fund. J81A (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 maxflow 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. 5468, 2002
DOI:
10.1006/jagm.2001.1203
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.
(
www.sciencedirect.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
Citation Context
(21)
...The results of [24] are very useful in the controllability analysis of a singleleader configuration; however, many realworld multiagent system applications require more than one leader to ensure controllability (the reader is referred to [25], [26], [
27
] for some relevant problems)...
...Various types of this problem with different objectives are investigated in the literature [30], [31], [26], [
27
]...
Saeid Jafari
,
et al.
Leader selection in multiagent systems subject to partial failure
...Although λSLP and κSLP are important, we only refer to several previous works [
1
,7] because this paper focuses on ˆ κSLP...
Takuro Fukunaga
.
Approximating Minimum Cost Source Location Problems with Local Vertex...
...For a given integer k, where k 1, we say that a set S V of vertices (called sources) covers v2 V if the edgeconnectivity between S and v is at least k. The source location problem is to nd a minimumsize source set S V covering all vertices in V . This problem has been studied widely [
2
, 3, 6, 7, 8, 10, 13, 15], and such problems are important in the design of networks resistant to the failure of edges...
Hiro Ito
,
et al.
The MultiCommodity Source Location Problems and the Price of Greed
...The source location problem is to find a minimumsize source set S ⊆ V covering all vertices in V. This problem, which has been studied widely (Bárászet al. 2005; Ishii et al. 2003; Ito et al. 2002, 2003, 2000; Ito and Yokoyama 1998; Nagamochi et al. 2001; Tamura et al. 1990), can be solved in polynomial time (
Arata et al. 2002;
Ito et al. 2000)...
...However, with respect to the source location problem (not maximumcover version), these cases can be solved in polynomial time (
Arata et al. 2002;
Bárászet al. 2005)...
Hiro Ito
.
Maximumcover source location problems with objective edgeconnectivit...
...(For other examples of location problems with connectivity requirements see [
1
, 6, 7, 8, 9, 10, 12, 13])...
Jan Van Den Heuvel
,
et al.
Transversals of subtree hypergraphs and the source location problem in...
References
(8)
Augmenting Undirected Edge Connectivity in Õ(n2) Time
(
Citations: 7
)
András A. Benczúr
,
David R. Karger
Journal:
Journal of Algorithms  JAL
, vol. 37, no. 1, pp. 236, 2000
A simple mincut algorithm
(
Citations: 150
)
Mechthild Stoer
,
Frank Wagner
Journal:
Journal of The ACM  JACM
, vol. 44, no. 4, pp. 585591, 1997
Locating Sources to Meet Flow Demands in Undirected Networks
(
Citations: 23
)
Kouji Arata
,
Satoru Iwata
,
Kazuhisa Makino
,
Satoru Fujishige
Conference:
Scandinavian Workshop on Algorithm Theory  SWAT
, pp. 300313, 2000
EdgeConnectivity Augmentation Problems
(
Citations: 124
)
Toshimasa Watanabe
,
Akira Nakamura
Journal:
Journal of Computer and System Sciences  JCSS
, vol. 35, no. 1, pp. 96144, 1987
Beyond the flow decomposition barrier
(
Citations: 162
)
Andrew V. Goldberg
,
Satish Rao
Journal:
Journal of The ACM  JACM
, vol. 45, no. 5, pp. 783797, 1998
Sort by:
Citations
(28)
Leader selection in multiagent systems subject to partial failure
Saeid Jafari
,
Amir Ajorlou
,
Amir G. Aghdam
Published in 2011.
Approximating Minimum Cost Source Location Problems with Local VertexConnectivity Demands
Takuro Fukunaga
Conference:
Theory and Applications of Models of Computation  TAMC
, pp. 428439, 2011
Greedy approximation for the source location problem with vertexconnectivity requirements in undirected graphs
(
Citations: 1
)
Toshimasa Ishii
Journal:
Journal of Discrete Algorithms  JDA
, vol. 7, no. 4, pp. 570578, 2009
The MultiCommodity Source Location Problems and the Price of Greed
Hiro Ito
,
Mike Paterson
Journal:
Journal of Graph Algorithms and Applications  JGAA
, vol. 13, no. 1, pp. 5573, 2009
Maximumcover source location problems with objective edgeconnectivity three
Hiro Ito
Journal:
Mathematical Methods of Operations Research  MATH METHODS OPER RES
, vol. 70, no. 1, pp. 183193, 2009