{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:26:19Z","timestamp":1742912779456,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662535356"},{"type":"electronic","value":"9783662535363"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-53536-3_22","type":"book-chapter","created":{"date-parts":[[2016,9,27]],"date-time":"2016-09-27T12:39:25Z","timestamp":1474979965000},"page":"257-268","source":"Crossref","is-referenced-by-count":4,"title":["On Directed Steiner Trees with Multiple Roots"],"prefix":"10.1007","author":[{"given":"Ond\u0159ej","family":"Such\u00fd","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,28]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.ic.2012.10.007","volume":"222","author":"P Berman","year":"2013","unstructured":"Berman, P., Bhattacharyya, A., Makarychev, K., Raskhodnikova, S., Yaroslavtsev, G.: Approximation algorithms for spanner problems and directed Steiner forest. Inf. Comput. 222, 93\u2013107 (2013)","journal-title":"Inf. Comput."},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: STOC 2007, pp. 67\u201374. ACM (2007)","DOI":"10.1145\/1250790.1250801"},{"issue":"1","key":"22_CR3","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.Y., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithms 33(1), 73\u201391 (1999)","journal-title":"J. Algorithms"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Hajiaghayi, M., Marx, D.: Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions). In: SODA 2014, pp. 1782\u20131801. SIAM (2014)","DOI":"10.1137\/1.9781611973402.129"},{"key":"22_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/978-3-319-03898-8_11","volume-title":"Parameterized and Exact Computation","author":"R Chitnis","year":"2013","unstructured":"Chitnis, R., Hajiaghayi, M.T., Kortsarz, G.: Fixed-parameter and approximation algorithms: a new look. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 110\u2013122. Springer, Heidelberg (2013)"},{"key":"22_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Switzerland (2015)"},{"key":"22_CR7","series-title":"Texts in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)"},{"key":"22_CR8","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"SE Dreyfus","year":"1972","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195\u2013207 (1972)","journal-title":"Networks"},{"issue":"4","key":"22_CR9","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1287\/moor.12.4.634","volume":"12","author":"RE Erickson","year":"1987","unstructured":"Erickson, R.E., Monma, C.L., Veinott Jr., A.F.: Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res. 12(4), 634\u2013664 (1987)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"22_CR10","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1137\/S0097539704441241","volume":"36","author":"J Feldman","year":"2006","unstructured":"Feldman, J., Ruhl, M.: The directed Steiner network problem is tractable for a constant number of terminals. SIAM J. Comput. 36(2), 543\u2013561 (2006)","journal-title":"SIAM J. Comput."},{"key":"22_CR11","unstructured":"Feldmann, A.E., Marx, D.: The complexity landscape of fixed-parameter directed Steiner network problems. In: ICALP 2016. LIPIcs, vol. 55, pp. 27:1\u201327:4. Dagstuhl (2016). http:\/\/dx.doi.org\/10.4230\/LIPIcs.ICALP.2016.27"},{"issue":"3","key":"22_CR12","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1007\/s00224-007-1324-4","volume":"41","author":"B Fuchs","year":"2007","unstructured":"Fuchs, B., Kern, W., M\u00f6lle, D., Richter, S., Rossmanith, P., Wang, X.: Dynamic programming for minimum Steiner trees. Theor. Comput. Syst. 41(3), 493\u2013500 (2007)","journal-title":"Theor. Comput. Syst."},{"issue":"4","key":"22_CR13","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"22_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"2","key":"22_CR15","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1137\/100794560","volume":"25","author":"J Guo","year":"2011","unstructured":"Guo, J., Niedermeier, R., Such\u00fd, O.: Parameterized complexity of arc-weighted directed Steiner problems. SIAM J. Discrete Math. 25(2), 583\u2013599 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"22_CR16","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1002\/net.3230010203","volume":"1","author":"SL Hakimi","year":"1971","unstructured":"Hakimi, S.L.: Steiner\u2019s problem in graphs and its implications. Networks 1, 113\u2013133 (1971)","journal-title":"Networks"},{"issue":"5","key":"22_CR17","doi-asserted-by":"crossref","first-page":"1494","DOI":"10.1137\/S0097539704445718","volume":"36","author":"E Halperin","year":"2007","unstructured":"Halperin, E., Kortsarz, G., Krauthgamer, R., Srinivasan, A., Wang, N.: Integrality ratio for group Steiner trees and directed Steiner trees. SIAM J. Comput. 36(5), 1494\u20131511 (2007)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"22_CR18","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"22_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1007\/978-3-642-40450-4_57","volume-title":"Algorithms \u2013 ESA 2013","author":"M Jones","year":"2013","unstructured":"Jones, M., Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Such\u00fd, O.: Parameterized complexity of directed Steiner tree on sparse graphs. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 671\u2013682. Springer, Heidelberg (2013)"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Kortsarz, G., Nutov, Z.: Approximating minimum cost connectivity problems. In: Handbook of Approximation Algorithms and Metaheuristics, chapt. 58. CRC (2007)","DOI":"10.1201\/9781420010749.ch58"},{"key":"22_CR21","first-page":"1477","volume":"12","author":"AY Levin","year":"1971","unstructured":"Levin, A.Y.: Algorithm for the shortest connection of a group of graph vertices. Sov. Math. Dokl. 12, 1477\u20131481 (1971)","journal-title":"Sov. Math. Dokl."},{"issue":"1","key":"22_CR22","doi-asserted-by":"crossref","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theor. Comput. 6(1), 85\u2013112 (2010)","journal-title":"Theor. Comput."},{"issue":"4","key":"22_CR23","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1007\/s00453-012-9630-x","volume":"65","author":"J Nederlof","year":"2013","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica 65(4), 868\u2013884 (2013)","journal-title":"Algorithmica"},{"issue":"4","key":"22_CR24","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"22_CR25","unstructured":"Such\u00fd, O.: On directed Steiner trees with multiple roots. CoRR abs\/1604.05103(2016). http:\/\/arxiv.org\/abs\/1604.05103"}],"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-662-53536-3_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T22:01:48Z","timestamp":1568412108000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53536-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662535356","9783662535363"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53536-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}