{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T12:18:11Z","timestamp":1790079491377,"version":"4.0.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642112652","type":"print"},{"value":"9783642112669","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11266-9_56","type":"book-chapter","created":{"date-parts":[[2009,12,7]],"date-time":"2009-12-07T09:04:58Z","timestamp":1260176698000},"page":"672-684","source":"Crossref","is-referenced-by-count":9,"title":["An Amortized Search Tree Analysis for k-Leaf Spanning Tree"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Raible","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"56_CR1","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/0-387-23830-1_8","volume-title":"Handbook of Comb. Opt.","author":"J. Blum","year":"2005","unstructured":"Blum, J., Ding, M., Thaeler, A., Cheng, X.: Connected Dominating Set in Sensor Networks and MANETs. In: Handbook of Comb. Opt., vol.\u00a0B, pp. 329\u2013369. Springer, Heidelberg (2005)"},{"key":"56_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/978-3-540-45138-9_20","volume-title":"Mathematical Foundations of Computer Science 2003","author":"P.S. Bonsma","year":"2003","unstructured":"Bonsma, P.S., Brueggemann, T., Woeginger, G.J.: A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol.\u00a02747, pp. 259\u2013268. Springer, Heidelberg (2003)"},{"key":"56_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-540-92248-3_7","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P.S. Bonsma","year":"2008","unstructured":"Bonsma, P.S., Zickfeld, F.: A 3\/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol.\u00a05344, pp. 66\u201377. Springer, Heidelberg (2008)"},{"key":"56_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/978-3-540-78773-0_46","volume-title":"LATIN 2008: Theoretical Informatics","author":"P.S. Bonsma","year":"2008","unstructured":"Bonsma, P.S., Zickfeld, F.: Spanning Trees with Many Leaves in Graphs without Diamond and Blossoms. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 531\u2013543. Springer, Heidelberg (2008)"},{"key":"56_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/978-3-540-24587-2_17","volume-title":"Algorithms and Computation","author":"J. Chen","year":"2003","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Labeled Search Trees and Amortized Analysis: Improved upper Bounds for NP-Hard Problems. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 148\u2013157. Springer, Heidelberg (2003)"},{"key":"56_CR6","doi-asserted-by":"crossref","unstructured":"Daligault, J., Gutin, G., Kim, E.J., Yeo, A.: FPT Algorithms and Kernels for the Directed k-Leaf Problem. Journal of Computer and System Sciences (2009), \n                    \n                      http:\/\/dx.doi.org\/10.1016\/j.jcss.2009.06.005","DOI":"10.1016\/j.jcss.2009.06.005"},{"key":"56_CR7","doi-asserted-by":"crossref","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, Heidelberg (1999)"},{"key":"56_CR8","first-page":"1","volume-title":"ACiD","author":"V. Estivill-Castro","year":"2005","unstructured":"Estivill-Castro, V., Fellows, M.R., Langston, M.A., Rosamond, F.A.: FPT is P-Time Extremal Structure I. In: ACiD, pp. 1\u201341. King\u2019s College Publications, London (2005)"},{"key":"56_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/978-3-642-11269-0_13","volume-title":"IWPEC 2009","author":"H. Fernau","year":"2009","unstructured":"Fernau, H., Langer, A., Liedloff, M., Kneis, J.: An Exact Algorithm for the Maximum Leaf Spanning Tree Problem. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 161\u2013172. Springer, Heidelberg (2009)"},{"key":"56_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-540-77891-2_14","volume-title":"WALCOM: Algorithms and Computation","author":"H. Fernau","year":"2008","unstructured":"Fernau, H., Raible, D.: Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs. In: Nakano, S.-i., Rahman, M. S. (eds.) WALCOM 2008. LNCS, vol.\u00a04921, pp. 144\u2013156. Springer, Heidelberg (2008)"},{"key":"56_CR11","unstructured":"Fernau, H., Gaspers, S., Raible, D.: Exact and Parameterized Algorithms for Max Internal Spanning Tree. In: WG (to appear, 2009)"},{"key":"56_CR12","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A Measure & Conquer Approach for the Analysis of Exact Algorithms. Journal of the ACM\u00a056(5) (2009)","DOI":"10.1145\/1552285.1552286"},{"issue":"2","key":"56_CR13","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00453-007-9145-z","volume":"52","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Solving Connected Dominating Set Faster than 2\n                    \n                      \n                    \n                    $^{\\mbox{{\\it n}}}$\n                  . Algorithmica\u00a052(2), 153\u2013166 (2008)","journal-title":"Algorithmica"},{"key":"56_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/978-3-540-92182-0_26","volume-title":"Algorithms and Computation","author":"J. Kneis","year":"2008","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: A New Algorithm for Finding Trees with Many Leaves. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 270\u2013281. Springer, Heidelberg (2008)"},{"key":"56_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1007\/978-3-642-02927-1_54","volume-title":"ICALP 2009, Part I","author":"I. Koutis","year":"2009","unstructured":"Koutis, I., Williams, R.: Limits and Applications of Group Algebras for Parameterized Problems. In: Albers, S., et al. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 653\u2013664. Springer, Heidelberg (2009)"},{"key":"56_CR16","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1006\/jagm.1998.0944","volume":"29","author":"H.-I. Lu","year":"1998","unstructured":"Lu, H.-I., Ravi, R.: Approximating Maximum Leaf Spanning Trees in Almost Linear Time. Journal of Algorithms\u00a029, 132\u2013141 (1998)","journal-title":"Journal of Algorithms"},{"key":"56_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/3-540-68530-8_37","volume-title":"Algorithms - ESA \u201998","author":"R. Solis-Oba","year":"1998","unstructured":"Solis-Oba, R.: 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 441\u2013452. Springer, Heidelberg (1998)"},{"key":"56_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TMC.2007.1034","volume":"6","author":"M.T. Thai","year":"2007","unstructured":"Thai, M.T., Wang, F., Liu, D., Zhu, S., Du, D.-Z.: Connected Dominating Sets in Wireless Networks Different Transmission Ranges. IEEE Trans. Mobile Computing\u00a06, 1\u201310 (2007)","journal-title":"IEEE Trans. Mobile Computing"},{"key":"56_CR19","unstructured":"Wahlstr\u00f6m, M.: Algorithms, Measures and Upper Bounds for Satisfiability and Related Problems. PhD Thesis, Department of Computer and Information Science, Link\u00f6pings Universitet, Sweden (2007)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2010: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11266-9_56","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,10]],"date-time":"2019-03-10T19:03:32Z","timestamp":1552244612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11266-9_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642112652","9783642112669"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11266-9_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}