{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:37:33Z","timestamp":1743140253228,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_20","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"243-255","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Spotting Trees with Few Leaves"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vikram","family":"Kamat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u0141ukasz","family":"Kowalik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"4","key":"20_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"1","key":"20_CR2","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1137\/110839229","volume":"43","author":"A Bj\u00f6rklund","year":"2014","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected Hamiltonicity. SIAM J. on Computing 43(1), 280\u2013299 (2014)","journal-title":"SIAM J. on Computing"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-540-70575-8_17","volume-title":"Automata, Languages and Programming","author":"A Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The travelling salesman problem in bounded degree graphs. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 198\u2013209. Springer, Heidelberg (2008)"},{"key":"20_CR4","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings (2010). CoRR, abs\/1007.1161"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Kamat, V., Kowalik, L., Zehavi, M.: Spotting trees with few leaves (2015). CoRR, abs\/1501.00563","DOI":"10.1007\/978-3-662-47672-7_20"},{"key":"20_CR6","unstructured":"Bj\u00f6rklund, A., Kaski, P., Kowalik, L.: Probably optimal graph motifs. In: Proc. STACS 2013. LIPIcs, vol. 20, pp. 20\u201331 (2013)"},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/978-3-662-44777-2_13","volume-title":"Algorithms - ESA 2014","author":"A Bj\u00f6rklund","year":"2014","unstructured":"Bj\u00f6rklund, A., Kaski, P., Kowalik, \u0141.: Fast witness extraction using a decision oracle. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 149\u2013160. Springer, Heidelberg (2014)"},{"issue":"6","key":"20_CR8","doi-asserted-by":"publisher","first-page":"2526","DOI":"10.1137\/080716475","volume":"38","author":"J Chen","year":"2009","unstructured":"Chen, J., Kneis, J., Lu, S., Molle, D., Richter, S., Rossmanith, P., Sze, S.H., Zhang, F.: Randomized divide-and-conquer: Improved path, matching, and packing algorithms. SIAM J. on Computing 38(6), 2526\u20132547 (2009)","journal-title":"SIAM J. on Computing"},{"issue":"7","key":"20_CR9","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1016\/j.jcss.2010.01.001","volume":"76","author":"N Cohen","year":"2010","unstructured":"Cohen, N., Fomin, F.V., Gutin, G., Kim, E.J., Saurabh, S., Yeo, A.: Algorithm for finding $$k$$-vertex out-trees and its application to $$k$$-internal out-branching problem. J. Comput. Syst. Sci. 76(7), 650\u2013662 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Proc. FOCS 2011, pp. 150\u2013159 (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"20_CR11","unstructured":"Daligault, J.: Combinatorial techniques for parameterized algorithms and kernels, with applications to multicut. PhD thesis, Universite Montpellier II (2011)"},{"key":"20_CR12","unstructured":"Demers, A., Downing, A.: Minimum leaf spanning tree. US Patent no. 6,105,018, August 2013"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"RA DeMillo","year":"1978","unstructured":"DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Inf. Process. Lett. 7, 193\u2013195 (1978)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"20_CR14","doi-asserted-by":"publisher","first-page":"61","DOI":"10.7155\/jgaa.00137","volume":"11","author":"D Eppstein","year":"2007","unstructured":"Eppstein, D.: The traveling salesman problem for cubic graphs. J. Graph Algorithms Appl. 11(1), 61\u201381 (2007)","journal-title":"J. Graph Algorithms Appl."},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Fomin, F., Lokshtanov, D., Saurabh, S.: Efficient computation of representative sets with applications in parameterized and exact agorithms. In: SODA, pp. 142\u2013151 (2014)","DOI":"10.1137\/1.9781611973402.10"},{"key":"20_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/978-3-662-44777-2_37","volume-title":"Algorithms - ESA 2014","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Representative sets of product families. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 443\u2013454. Springer, Heidelberg (2014)"},{"key":"20_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22015-9","volume-title":"Approximation algorithms and semidefinite programming","author":"B G\u00e4rtner","year":"2012","unstructured":"G\u00e4rtner, B., Mat\u01d2usek, J.: Approximation algorithms and semidefinite programming. Springer, Heidelberg (2012)"},{"issue":"6","key":"20_CR18","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42(6), 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"issue":"2","key":"20_CR19","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.jda.2005.03.002","volume":"4","author":"F Grandoni","year":"2006","unstructured":"Grandoni, F.: A note on the complexity of minimum dominating set. J. Discrete Algorithms 4(2), 209\u2013214 (2006)","journal-title":"J. Discrete Algorithms"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Gebauer, H.: On the number of hamilton cycles in bounded degree graphs. In: Proc. ANALCO 2008, pp. 241\u2013248 (2008)","DOI":"10.1137\/1.9781611972986.8"},{"issue":"2","key":"20_CR21","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1137\/050648237","volume":"19","author":"N Gvozdenovic","year":"2008","unstructured":"Gvozdenovic, N., Laurent, M.: The operator psi for the chromatic number of a graph. SIAM Journal on Optimization 19(2), 572\u2013591 (2008)","journal-title":"SIAM Journal on Optimization"},{"key":"20_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-73545-8_13","volume-title":"Computing and Combinatorics","author":"K Iwama","year":"2007","unstructured":"Iwama, K., Nakashima, T.: An improved exact algorithm for cubic graph TSP. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 108\u2013117. Springer, Heidelberg (2007)"},{"key":"20_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/978-3-540-70575-8_47","volume-title":"Automata, Languages and Programming","author":"I Koutis","year":"2008","unstructured":"Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 575\u2013586. Springer, Heidelberg (2008)"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Li, W., Wang, J., Chen, J., Cao, Y.: A $$2k$$-vertex kernel for maximum internal spanning tree (2014). CoRR abs\/1412.8296","DOI":"10.1007\/978-3-319-21840-3_41"},{"key":"20_CR25","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0095-8956(75)90089-1","volume":"19","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: Three short proofs in graph theory. J. Combin. Theory Ser. 19, 269\u2013271 (1975)","journal-title":"J. Combin. Theory Ser."},{"key":"20_CR26","first-page":"239","volume":"25","author":"B Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. Annals of Discrete Mathematics 25, 239\u2013254 (1985)","journal-title":"Annals of Discrete Mathematics"},{"key":"20_CR27","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. 5555, pp. 713\u2013725. Springer, Heidelberg (2009)"},{"issue":"4","key":"20_CR28","doi-asserted-by":"publisher","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":"3","key":"20_CR29","first-page":"308","volume":"12","author":"E Prieto","year":"2005","unstructured":"Prieto, E., Sloper, C.: Reducing to independent set structure - the case of $$k$$-internal spanning tree. Nord. J. Comput. 12(3), 308\u2013318 (2005)","journal-title":"Nord. J. Comput."},{"issue":"1","key":"20_CR30","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s00453-011-9575-5","volume":"65","author":"D Raible","year":"2013","unstructured":"Raible, D., Fernau, H., Gaspers, D., Liedloff, M.: Exact and parameterized algorithms for max internal spanning tree. Algorithmica 65(1), 95\u2013128 (2013)","journal-title":"Algorithmica"},{"key":"20_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/11785293_17","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"I Razgon","year":"2006","unstructured":"Razgon, I.: Exact computation of maximum induced forest. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 160\u2013171. Springer, Heidelberg (2006)"},{"issue":"4","key":"20_CR32","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"key":"20_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"786","DOI":"10.1007\/978-3-662-44777-2_65","volume-title":"Algorithms - ESA 2014","author":"H Shachnai","year":"2014","unstructured":"Shachnai, H., Zehavi, M.: Representative families: a unified tradeoff-based approach. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 786\u2013797. Springer, Heidelberg (2014)"},{"issue":"6","key":"20_CR34","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length $$k$$ in $$O^*(2^k)$$ time. Inf. Process. Lett. 109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."},{"key":"20_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-319-03898-8_30","volume-title":"Parameterized and Exact Computation","author":"M Zehavi","year":"2013","unstructured":"Zehavi, M.: Algorithms for k-internal out-branching. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 361\u2013373. Springer, Heidelberg (2013)"},{"key":"20_CR36","unstructured":"Zehavi, M.: Mixing color coding-related techniques (2014). CoRR, abs\/1410.5062"},{"key":"20_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol. 72, pp. 216\u2013226. Springer, Heidelberg (1979)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T13:27:32Z","timestamp":1674566852000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}