{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:30:31Z","timestamp":1725456631950},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642346101"},{"type":"electronic","value":"9783642346118"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34611-8_23","type":"book-chapter","created":{"date-parts":[[2012,10,22]],"date-time":"2012-10-22T08:42:25Z","timestamp":1350895345000},"page":"215-224","source":"Crossref","is-referenced-by-count":0,"title":["Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications"],"prefix":"10.1007","author":[{"given":"Tomoya","family":"Hibi","sequence":"first","affiliation":[]},{"given":"Toshihiro","family":"Fujito","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: An improved LP-based approximation for Steiner tree. In: Proc. 42nd STOC, pp. 583\u2013592 (2010)","DOI":"10.1145\/1806689.1806769"},{"key":"23_CR2","unstructured":"Berman, P., Ramaiyer, V.: Improved approximations for the Steiner tree problem. In: Proc. 3rd SODA, pp. 325\u2013334 (1992)"},{"issue":"3","key":"23_CR3","doi-asserted-by":"publisher","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. Theory Comput. Syst.\u00a0406(3), 207\u2013214 (2008)","journal-title":"Theory Comput. Syst."},{"key":"23_CR4","doi-asserted-by":"publisher","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\u00a033, 73\u201391 (1999)","journal-title":"J. Algorithms"},{"key":"23_CR5","doi-asserted-by":"publisher","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. Opt.\u00a09, 281\u2013294 (2005)","journal-title":"J. Comb. Opt."},{"issue":"4","key":"23_CR6","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"23_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/11786986_38","volume-title":"Automata, Languages and Programming","author":"T. Fujito","year":"2006","unstructured":"Fujito, T.: How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 431\u2013442. Springer, Heidelberg (2006)"},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proc. 35th STOC, pp. 585\u2013594 (2003)","DOI":"10.1145\/780542.780628"},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"23_CR10","doi-asserted-by":"publisher","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. Comb. Opt.\u00a01, 47\u201365 (1997)","journal-title":"J. Comb. Opt."},{"key":"23_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/3-540-44436-X_19","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"J. K\u00f6nemann","year":"2000","unstructured":"K\u00f6nemann, J., Konjevod, G., Parekh, O., Sinha, A.: Improved Approximations for Tour and Tree Covers. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol.\u00a01913, pp. 184\u2013193. Springer, Heidelberg (2000)"},{"key":"23_CR12","unstructured":"Konjevod, G.: Directed Steiner trees, linear programs and randomized rounding, 8 pages (2005) (manuscript)"},{"key":"23_CR13","doi-asserted-by":"publisher","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 Applied Mathematics\u00a093, 265\u2013285 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-642-17461-2_12","volume-title":"Combinatorial Optimization and Applications","author":"V.H. Nguyen","year":"2010","unstructured":"Nguyen, V.H.: Approximation Algorithm for the Minimum Directed Tree Cover. In: Wu, W., Daescu, O. (eds.) COCOA 2010, Part II. LNCS, vol.\u00a06509, pp. 144\u2013159. Springer, Heidelberg (2010)"},{"key":"23_CR15","unstructured":"Rothvo\u00df, T.: Directed Steiner tree and the Lasserre hierarchy. ArXiv e-prints (November 2011)"},{"key":"23_CR16","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: Proc. 29th STOC, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"23_CR17","unstructured":"Rajagopalan, S., Vazirani, V.V.: On the bidirected cut relaxation for the metric Steiner tree problem. In: Proc. 10th SODA, pp. 742\u2013751 (1999)"},{"key":"23_CR18","doi-asserted-by":"publisher","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.\u00a019, 122\u2013134 (2005)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"23_CR19","doi-asserted-by":"publisher","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. Inform. Process. Lett.\u00a014(5), 233\u2013235 (1982)","journal-title":"Inform. Process. Lett."},{"key":"23_CR20","doi-asserted-by":"publisher","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\u00a018, 99\u2013110 (1997)","journal-title":"Algorithmica"},{"key":"23_CR21","doi-asserted-by":"publisher","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\u00a09, 463\u2013470 (1993)","journal-title":"Algorithmica"},{"key":"23_CR22","unstructured":"Zosin, L., Khuller, S.: On directed Steiner trees. In: Proc. 13th SODA, pp. 59\u201363 (2002)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34611-8_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:00:45Z","timestamp":1620133245000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34611-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642346101","9783642346118"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34611-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}