{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:55Z","timestamp":1761611215682},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,9,22]],"date-time":"2007-09-22T00:00:00Z","timestamp":1190419200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,4]]},"DOI":"10.1007\/s00453-007-9012-y","type":"journal-article","created":{"date-parts":[[2007,9,21]],"date-time":"2007-09-21T15:33:23Z","timestamp":1190388803000},"page":"555-583","source":"Crossref","is-referenced-by-count":10,"title":["Minimum Cost Source Location Problems with Flow Requirements"],"prefix":"10.1007","volume":"50","author":[{"given":"Mariko","family":"Sakashita","sequence":"first","affiliation":[]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[]},{"given":"Satoru","family":"Fujishige","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,9,22]]},"reference":[{"key":"9012_CR1","unstructured":"Andreev, K., Garrod, C., Maggs, B.: Simultaneous source location. SCS Technical Report CMU-CS-03-162, Carnegie Mellon University, Pittsburgh"},{"key":"9012_CR2","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1006\/jagm.2001.1203","volume":"42","author":"K. Arata","year":"2002","unstructured":"Arata, K., Iwata, S., Makino, K., Fujishige, S.: Locating sources to meet flow demands in undirected networks. J. Algorithms 42, 54\u201368 (2002)","journal-title":"J. Algorithms"},{"key":"9012_CR3","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/j.orl.2004.07.005","volume":"33","author":"M. B\u00e1r\u00e1sz","year":"2005","unstructured":"B\u00e1r\u00e1sz, M., Becker, J., Frank, A.: An algorithm for source location in directed graphs. Oper. Res. Lett. 33, 221\u2013230 (2005)","journal-title":"Oper. Res. Lett."},{"key":"9012_CR4","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln\u2009n for approximating set cover. J. ACM 45, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"9012_CR5","first-page":"480","volume":"E83-D","author":"T. Fujito","year":"2000","unstructured":"Fujito, T.: Approximation algorithms for submodular set cover with applications. IEICE Trans. E83-D, 480\u2013487 (2000)","journal-title":"IEICE Trans."},{"key":"9012_CR6","unstructured":"Goel, A., Estrin, D.: Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk. In: Proceedings of 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 499\u2013505 (2003)"},{"key":"9012_CR7","volume-title":"Computers and Intractability: A Guide to the Theory NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory NP-Completeness. Freeman, New York (1979)"},{"key":"9012_CR8","unstructured":"Ishii, T., Fujita, H., Nagamochi, H.: Source location problem with local 3-vertex-connectivity requirements. In: Proceedings of 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 368\u2013377 (2003)"},{"key":"9012_CR9","unstructured":"Ishii, T., Fujita, H., Nagamochi, H.: Minimum cost source location problem with local 3-vertex-connectivity requirements. In: Computing Theory: The Australian Theory Symposium, pp. 97\u2013105 (2005)"},{"key":"9012_CR10","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1002\/net.10034","volume":"40","author":"H. Ito","year":"2002","unstructured":"Ito, H., Ito, M., Itatsu, Y., Uehara, H., Yokoyama, M.: Source location problems considering vertex-connectivity and edge-connectivity simultaneously. Networks 40, 63\u201370 (2002)","journal-title":"Networks"},{"key":"9012_CR11","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1080\/1055-6780309510593","volume":"18","author":"H. Ito","year":"2003","unstructured":"Ito, H., Makino, K., Arata, K., Honami, S., Itatsu, Y., Fujishige, S.: Source location problem with flow requirements in directed networks. Optim. Methods Softw. 18, 427\u2013435 (2003)","journal-title":"Optim. Methods Softw."},{"key":"9012_CR12","first-page":"551","volume-title":"Handbooks in OR & MS, vol. 8","author":"M. Labbe","year":"1995","unstructured":"Labbe, M., Peeters, D., Thisse, J.-F.: Location on networks. In: Ball, M.O., et al. (eds.) Handbooks in OR & MS, vol. 8, pp.\u00a0551\u2013624. North-Holland, Amsterdam (1995)"},{"key":"9012_CR13","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41, 960\u2013981 (1994)","journal-title":"J. ACM"},{"key":"9012_CR14","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0020-0190(01)00183-1","volume":"80","author":"H. Nagamochi","year":"2001","unstructured":"Nagamochi, H., Ishii, T., Ito, H.: Minimum cost source location problem with vertex-connectivity requirements in digraphs. Inform. Process. Lett. 80, 287\u2013294 (2001)","journal-title":"Inform. Process. Lett."},{"key":"9012_CR15","doi-asserted-by":"crossref","unstructured":"Sakashita, M., Makino, K., Fujishige, S.: Minimizing a monotone concave function with laminar covering constraints. In: ISAAC 2005. LNCS, vol.\u00a03827, pp.\u00a071\u201381 (2005), Discrete Appl. Math. (2007, in press)","DOI":"10.1007\/11602613_9"},{"key":"9012_CR16","doi-asserted-by":"crossref","unstructured":"Sakashita, M., Makino, K., Fujishige, S.: Minimum cost source location problems with flow requirements. In: LATIN 2006. LNCS, vol.\u00a03887, pp.\u00a0769\u2013780 (2006)","DOI":"10.1007\/11682462_70"},{"key":"9012_CR17","first-page":"1989","volume":"E73","author":"H. Tamura","year":"1990","unstructured":"Tamura, H., Sengoku, M., Shinoda, S., Abe, T.: Location problems on undirected flow networks. IEICE Trans. E73, 1989\u20131993 (1990)","journal-title":"IEICE Trans."},{"key":"9012_CR18","first-page":"678","volume":"E75-A","author":"H. Tamura","year":"1992","unstructured":"Tamura, H., Sengoku, M., Shinoda, S., Abe, T.: Some covering problems in location theory on flow networks. IEICE Trans. E75-A, 678\u2013683 (1992)","journal-title":"IEICE Trans."},{"key":"9012_CR19","first-page":"863","volume":"J81-A","author":"H. Tamura","year":"1998","unstructured":"Tamura, H., Sugawara, H., Sengoku, M., Shinoda, S.: Plural cover problem on undirected flow networks. IEICE Trans. J81-A, 863\u2013869 (1998) (in Japanese)","journal-title":"IEICE Trans."},{"key":"9012_CR20","unstructured":"van\u00a0den Heuvel, J., Johnson, M.: Transversals of subtree hypergraphs and the source location problem in digraphs. CDAM Research Report, LSE-CDAM-2004-10, London School of Economics"},{"key":"9012_CR21","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"L.A. Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9012-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9012-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9012-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:44:59Z","timestamp":1559123099000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9012-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,22]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,4]]}},"alternative-id":["9012"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9012-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,22]]}}}