{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T05:57:01Z","timestamp":1726207021097},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_57","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"671-682","source":"Crossref","is-referenced-by-count":11,"title":["Parameterized Complexity of Directed Steiner Tree on Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Mark","family":"Jones","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ond\u0159ej","family":"Such\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"57_CR1","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/s00453-008-9204-0","volume":"54","author":"N. Alon","year":"2009","unstructured":"Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica\u00a054(4), 544\u2013556 (2009)","journal-title":"Algorithmica"},{"issue":"4","key":"57_CR2","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M.W. Bern","year":"1989","unstructured":"Bern, M.W., Plassmann, P.E.: The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett.\u00a032(4), 171\u2013176 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"9","key":"57_CR3","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1006\/eujc.1997.0188","volume":"19","author":"B. Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B., Thomason, A.: Proof of a conjecture of Mader, Erd\u00f6s and Hajnal on topological complete subgraphs. Eur. J. Comb.\u00a019(9), 883\u2013887 (1998)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"57_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.-Y., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithms\u00a033(1), 73\u201391 (1999)","journal-title":"J. Algorithms"},{"key":"57_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-642-02927-1_28","volume-title":"Automata, Languages and Programming","author":"E.D. Demaine","year":"2009","unstructured":"Demaine, E.D., Hajiaghayi, M., Klein, P.N.: Node-weighted Steiner tree and group Steiner tree in planar graphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 328\u2013340. Springer, Heidelberg (2009)"},{"key":"57_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"issue":"4","key":"57_CR7","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math.\u00a032(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"57_CR8","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, San Francisco (1979)"},{"key":"57_CR9","doi-asserted-by":"crossref","unstructured":"Grohe, M., Marx, D.: Structure theorem and isomorphism test for graphs with excluded topological subgraphs. In: STOC, pp. 173\u2013192 (2012)","DOI":"10.1145\/2213977.2213996"},{"issue":"5","key":"57_CR10","doi-asserted-by":"publisher","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.\u00a036(5), 1494\u20131511 (2007)","journal-title":"SIAM J. Comput."},{"key":"57_CR11","doi-asserted-by":"crossref","unstructured":"Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. North-Holland (1992)","DOI":"10.1002\/net.3230220105"},{"issue":"4","key":"57_CR12","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci.\u00a063(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"57_CR13","doi-asserted-by":"crossref","unstructured":"Jones, M., Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Such\u00fd, O.: Parameterized complexity of directed steiner tree on sparse graphs. CoRR, abs\/1210.0260 (2012)","DOI":"10.1007\/978-3-642-40450-4_57"},{"issue":"1","key":"57_CR14","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P. Klein","year":"1995","unstructured":"Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted steiner trees. Journal of Algorithms\u00a019(1), 104\u2013115 (1995)","journal-title":"Journal of Algorithms"},{"key":"57_CR15","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1017\/S096354830000184X","volume":"5","author":"J. Koml\u00f3s","year":"1996","unstructured":"Koml\u00f3s, J., Szemer\u00e9di, E.: Topological cliques in graphs 2. Combinatorics, Probability & Computing\u00a05, 79\u201390 (1996)","journal-title":"Combinatorics, Probability & Computing"},{"key":"57_CR16","unstructured":"Korte, B., Pr\u00f6mel, H.J., Steger, A.: Steiner trees in VLSI-layout. In: Paths, Flows and VLSI-Layout, pp. 185\u2013214 (1990)"},{"key":"57_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-3-642-11440-3_25","volume-title":"WALCOM: Algorithms and Computation","author":"N. Misra","year":"2010","unstructured":"Misra, N., Philip, G., Raman, V., Saurabh, S., Sikdar, S.: FPT algorithms for connected feedback vertex set. In: Rahman, M. S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol.\u00a05942, pp. 269\u2013280. Springer, Heidelberg (2010)"},{"issue":"2","key":"57_CR18","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/s00224-007-9089-3","volume":"43","author":"D. M\u00f6lle","year":"2008","unstructured":"M\u00f6lle, D., Richter, S., Rossmanith, P.: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Theory Comput. Syst.\u00a043(2), 234\u2013253 (2008)","journal-title":"Theory Comput. Syst."},{"key":"57_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/978-3-642-02927-1_59","volume-title":"Automata, Languages and Programming","author":"J. Nederlof","year":"2009","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using m\u00f6bius inversion: Improving on steiner tree and related problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 713\u2013725. Springer, Heidelberg (2009)"},{"key":"57_CR20","doi-asserted-by":"crossref","unstructured":"Pr\u00f6mel, H.J., Steger, A.: The Steiner Tree Problem; a Tour through Graphs, Algorithms, and Complexity. Vieweg (2002)","DOI":"10.1007\/978-3-322-80291-0"},{"issue":"1","key":"57_CR21","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(1), 99\u2013110 (1997)","journal-title":"Algorithmica"},{"key":"57_CR22","unstructured":"Zosin, L., Khuller, S.: On directed Steiner trees. In: Proc. SODA 2002, pp. 59\u201363 (2002)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T12:55:50Z","timestamp":1558011350000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}