Simultaneous source location
Publication
, Journal Article
Andreev, K; Garrod, C; Maggs, B; Meyerson, A
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 2004
We consider the problem of Simultaneous Source Location -selecting locations for sources in a capacitated graph such that a given set of demands can be satisfied. We give an exact algorithm for trees and show how this can be combined with a result of Räcke to give a solution that exceeds edge capacities by at most O(log2 n log log n), where n is the number of nodes. On graphs of bounded treewidth, we show the problem is still NP-Hard, but we are able to give a PTAS with at most O(1+ε) violation of the capacities, or a (k+1)-approximation with exact capacities, where k is the treewidth and ε can be made arbitrarily small. © Springer-Verlag 2004.
Duke Scholars
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
January 1, 2004
Volume
3122
Start / End Page
13 / 26
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Andreev, K., Garrod, C., Maggs, B., & Meyerson, A. (2004). Simultaneous source location. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3122, 13–26. https://doi.org/10.1007/978-3-540-27821-4_2
Andreev, K., C. Garrod, B. Maggs, and A. Meyerson. “Simultaneous source location.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3122 (January 1, 2004): 13–26. https://doi.org/10.1007/978-3-540-27821-4_2.
Andreev K, Garrod C, Maggs B, Meyerson A. Simultaneous source location. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2004 Jan 1;3122:13–26.
Andreev, K., et al. “Simultaneous source location.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3122, Jan. 2004, pp. 13–26. Scopus, doi:10.1007/978-3-540-27821-4_2.
Andreev K, Garrod C, Maggs B, Meyerson A. Simultaneous source location. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2004 Jan 1;3122:13–26.
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
Publication Date
January 1, 2004
Volume
3122
Start / End Page
13 / 26
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences