{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T06:58:35Z","timestamp":1711436315473},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,2,12]],"date-time":"2015-02-12T00:00:00Z","timestamp":1423699200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00453-015-9973-1","type":"journal-article","created":{"date-parts":[[2015,2,11]],"date-time":"2015-02-11T09:24:16Z","timestamp":1423646656000},"page":"778-786","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications"],"prefix":"10.1007","volume":"74","author":[{"given":"Tomoya","family":"Hibi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshihiro","family":"Fujito","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,2,12]]},"reference":[{"issue":"3","key":"9973_CR1","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1006\/jagm.1994.1041","volume":"17","author":"P Berman","year":"1994","unstructured":"Berman, P., Ramaiyer, V.: Improved approximations for the Steiner tree problem. J. Algorithms 17(3), 381\u2013408 (1994)","journal-title":"J. Algorithms"},{"key":"9973_CR2","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvoss, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1\u20136:33 (2013)","DOI":"10.1145\/2432622.2432628"},{"key":"9973_CR3","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/s10878-005-1412-9","volume":"9","author":"G Calinescu","year":"2005","unstructured":"Calinescu, G., Zelikovsky, A.: The polymatroid Steiner problems. J. Comb. Optim. 9, 281\u2013294 (2005)","journal-title":"J. Comb. Optim."},{"key":"9973_CR4","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M Charikar","year":"1999","unstructured":"Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner tree problems. J. Algorithms 33, 73\u201391 (1999)","journal-title":"J. Algorithms"},{"issue":"3","key":"9973_CR5","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.tcs.2008.06.046","volume":"406","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The Steiner tree problem on graphs: inapproximability results. Theor. Comput. Sci. 406(3), 207\u2013214 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9973_CR6","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 n$$ ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"2","key":"9973_CR7","doi-asserted-by":"crossref","first-page":"16:1","DOI":"10.1145\/2151171.2151179","volume":"8","author":"T Fujito","year":"2012","unstructured":"Fujito, T.: How to trim a MST: a 2-approximation algorithm for minimum cost tree cover. ACM Trans. Algorithms 8(2), 16:1\u201316:11 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"9973_CR8","doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceedings of the 35th Symposium on Theory of Computing, pp. 585\u2013594. (2003)","DOI":"10.1145\/780542.780628"},{"key":"9973_CR9","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"9973_CR10","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1023\/A:1009758919736","volume":"1","author":"M Karpinski","year":"1997","unstructured":"Karpinski, M., Zelikovsky, A.Z.: New approximation algorithms for the Steiner tree problem. J. Combin. Optim. 1, 47\u201365 (1997)","journal-title":"J. Combin. Optim."},{"issue":"3","key":"9973_CR11","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/s00453-003-1071-0","volume":"38","author":"J K\u00f6nemann","year":"2004","unstructured":"K\u00f6nemann, J., Konjevod, G., Parekh, O., Sinha, A.: Improved approximations for tour and tree covers. Algorithmica 38(3), 441\u2013449 (2004)","journal-title":"Algorithmica"},{"key":"9973_CR12","unstructured":"Konjevod, G.: Directed Steiner trees, linear programs and randomized rounding. Manuscript, 8 pages (2005)"},{"key":"9973_CR13","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/S0166-218X(99)00111-0","volume":"93","author":"G Kortsarz","year":"1999","unstructured":"Kortsarz, G., Peleg, D.: Approximating the weight of shallow Steiner trees. Discrete Appl. Math. 93, 265\u2013285 (1999)","journal-title":"Discrete Appl. Math."},{"key":"9973_CR14","unstructured":"Rajagopalan, S., Vazirani, V.V.: On the bidirected cut relaxation for the metric Steiner tree problem. In: Proceedings of the 10th Symposium on Discrete Algorithms, pp. 742\u2013751. (1999)"},{"key":"9973_CR15","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th Symposium on Theory of Computing, pp. 475\u2013484. (1997)","DOI":"10.1145\/258533.258641"},{"key":"9973_CR16","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19, 122\u2013134 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"9973_CR17","unstructured":"Rothvo\u00df, T.: Directed Steiner tree and the Lasserre hierarchy. arXiv:1111.5473 (2011)"},{"issue":"5","key":"9973_CR18","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"C Savage","year":"1982","unstructured":"Savage, C.: Depth-first search and the vertex cover problem. Inf. Process. Lett. 14(5), 233\u2013235 (1982)","journal-title":"Inf. Process. Lett."},{"key":"9973_CR19","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: An 11\/6-approximation algorithm for the network Steiner problem. Algorithmica 9, 463\u2013470 (1993)","journal-title":"Algorithmica"},{"key":"9973_CR20","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02523690","volume":"18","author":"A Zelikovsky","year":"1997","unstructured":"Zelikovsky, A.: A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica 18, 99\u2013110 (1997)","journal-title":"Algorithmica"},{"key":"9973_CR21","unstructured":"Zosin, L., Khuller, S.: On directed Steiner trees. In: Proceedings of the 13th Symposium on Discrete Algorithms, pp. 59\u201363. (2002)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9973-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9973-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9973-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,20]],"date-time":"2019-08-20T17:09:51Z","timestamp":1566320991000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9973-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,12]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9973"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9973-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,12]]}}}