{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T21:21:33Z","timestamp":1743110493628,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319035772"},{"type":"electronic","value":"9783319035789"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03578-9_26","type":"book-chapter","created":{"date-parts":[[2013,11,8]],"date-time":"2013-11-08T08:52:11Z","timestamp":1383900731000},"page":"310-321","source":"Crossref","is-referenced-by-count":6,"title":["Steiner Problems with Limited Number of Branching Nodes"],"prefix":"10.1007","author":[{"given":"Dimitri","family":"Watel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc-Antoine","family":"Weisser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C\u00e9dric","family":"Bentz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominique","family":"Barth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Cheng, X., Du, D.Z.: Steiner trees in industry, vol.\u00a011. Kluwer (2001)","DOI":"10.1007\/978-1-4613-0255-1"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Vo\u00df, S.: Steiner tree problems in telecommunications, pp. 459\u2013492 (January 2006)","DOI":"10.1007\/978-0-387-30165-5_18"},{"key":"26_CR3","unstructured":"Rugeli, J., Novak, R.: Steiner tree algorithms for multicast protocols (1995)"},{"key":"26_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/978-3-642-01399-7_67","volume-title":"NETWORKING 2009","author":"V. Reinhard","year":"2009","unstructured":"Reinhard, V., Tomasik, J., Barth, D., Weisser, M.-A.: Bandwidth Optimization for Multicast Transmissions in Virtual Circuit Networks. In: Fratta, L., Schulzrinne, H., Takahashi, Y., Spaniol, O. (eds.) NETWORKING 2009. LNCS, vol.\u00a05550, pp. 859\u2013870. Springer, Heidelberg (2009)"},{"issue":"8","key":"26_CR5","doi-asserted-by":"publisher","first-page":"2097","DOI":"10.1016\/j.comnet.2012.02.005","volume":"56","author":"V. Reinhard","year":"2012","unstructured":"Reinhard, V., Cohen, J., Tomasik, J., Barth, D., Weisser, M.A.: Optimal configuration of an optical network providing predefined multicast transmissions. Comput. Netw.\u00a056(8), 2097\u20132106 (2012)","journal-title":"Comput. Netw."},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/3-540-45465-9_31","volume-title":"Automata, Languages and Programming","author":"L. Gargano","year":"2002","unstructured":"Gargano, L., Hell, P., Stacho, L., Vaccaro, U.: Spanning trees with bounded number of branch vertices. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 355\u2013365. Springer, Heidelberg (2002)"},{"issue":"3","key":"26_CR7","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0377-2217(02)00359-4","volume":"147","author":"J.J. Salazar-Gonz\u00e1lez","year":"2003","unstructured":"Salazar-Gonz\u00e1lez, J.J.: The Steiner cycle polytope. EJOR\u00a0147(3), 671\u2013679 (2003)","journal-title":"EJOR"},{"issue":"6+","key":"26_CR8","first-page":"1349","volume":"29","author":"M. Steinov\u00e1","year":"2010","unstructured":"Steinov\u00e1, M.: Approximability of the Minimum Steiner Cycle Problem. Computing and Informatics\u00a029(6+), 1349\u20131357 (2010)","journal-title":"Computing and Informatics"},{"issue":"111","key":"26_CR9","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoretical Computer Science\u00a010(111), 111\u2013121 (1980)","journal-title":"Theoretical Computer Science"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.: The disjoint paths problem. Journal of Combinatorial Theory, Series B, 65\u2013110 (1995)","DOI":"10.1006\/jctb.1995.1006"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Schrijver, A.: Finding k disjoint paths in a directed planar graph. SIAM Journal on Computing, 1\u201310 (1994)","DOI":"10.1137\/S0097539792224061"},{"key":"26_CR12","unstructured":"Scheffler, P.: A Practical Linear Time Algorithm for Disjoint Paths in Graphs with Bounded Tree Width. Technical Report 396\/1994, Fachbereich Mathematik (1994)"},{"issue":"2","key":"26_CR13","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L. Kou","year":"1981","unstructured":"Kou, L., Markowsky, G., Berman, L.: A fast algorithm for steiner trees. Acta informatica\u00a015(2), 141\u2013145 (1981)","journal-title":"Acta informatica"},{"issue":"5","key":"26_CR14","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(5), 463\u2013470 (1993)","journal-title":"Algorithmica"},{"key":"26_CR15","unstructured":"Hougardy, S., Pr\u00f6mel, H.: A 1.598 approximation algorithm for the Steiner problem in graphs. In: Proc. SODA, pp. 448\u2013453 (1999)"},{"key":"26_CR16","first-page":"227","volume":"5","author":"D. Du","year":"2000","unstructured":"Du, D., Lu, B., Ngo, H., Pardalos, P.: Steiner tree problems. Encyclopedia of Optimization\u00a05, 227\u2013290 (2000)","journal-title":"Encyclopedia of Optimization"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Hsu, T.S., Tsai, K., Wang, D., Lee, D.: Steiner problems on directed acyclic graphs. Computing and Combinatorics, 21\u201330 (1996)","DOI":"10.1007\/3-540-61332-3_135"},{"key":"26_CR18","unstructured":"Charikar, M., et al.: Approximation algorithms for directed steiner problems. In: Proc. SODA, pp. 192\u2013200 (1998)"},{"key":"26_CR19","first-page":"1409","volume":"22","author":"E. Ming-IHsieh","year":"2006","unstructured":"Ming-IHsieh, E., Tsai, M.: Fasterdsp: A faster approximation algorithm for directed steiner tree problem. JISE\u00a022, 1409\u20131425 (2006)","journal-title":"JISE"},{"key":"26_CR20","unstructured":"Rothvo\u00df, T.: Directed steiner tree and the lasserre hierarchy. CoRR abs\/1111.5473 (2011)"},{"issue":"4","key":"26_CR21","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. of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"J. of the ACM"},{"key":"26_CR22","doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proc. STOC, pp. 585\u2013594. ACM (2003)","DOI":"10.1145\/780542.780628"},{"key":"26_CR23","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group steiner tree problem. In: Proc. SODA, pp. 253\u2013259 (1998)"},{"key":"26_CR24","doi-asserted-by":"crossref","unstructured":"Ding, B., Yu, J.X., Wang, S., Qin, L., Zhang, X., Lin, X.: Finding top-k min-cost connected trees in databases. In: Chirkova, R., Dogac, A., \u00d6zsu, M.T., Sellis, T.K. (eds.) ICDE, pp. 836\u2013845. IEEE (2007)","DOI":"10.1109\/ICDE.2007.367929"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., Laekhanukit, B., Naves, G., Vetta, A.: Approximating rooted steiner networks. In: Proc. SODA, pp. 1499\u20131511 (2012)","DOI":"10.1137\/1.9781611973099.119"},{"key":"26_CR26","unstructured":"Watel, D., Weisser, M.A., Bentz, C.: Inapproximability proof of DSTLB and USTLB in planar graphs, \n                    \n                      http:\/\/hal-supelec.archives-ouvertes.fr\/hal-00793424"},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity, vol.\u00a03. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"4","key":"26_CR28","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1145\/76359.76368","volume":"36","author":"A.V. Goldberg","year":"1989","unstructured":"Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by canceling negative cycles. Journal of the ACM\u00a036(4), 873\u2013886 (1989)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03578-9_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T23:59:29Z","timestamp":1558655969000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03578-9_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319035772","9783319035789"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03578-9_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}