{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:41:45Z","timestamp":1725522105916},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540922476"},{"type":"electronic","value":"9783540922483"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"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":[[2008]]},"DOI":"10.1007\/978-3-540-92248-3_7","type":"book-chapter","created":{"date-parts":[[2008,12,4]],"date-time":"2008-12-04T13:36:17Z","timestamp":1228397777000},"page":"66-77","source":"Crossref","is-referenced-by-count":3,"title":["A 3\/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs"],"prefix":"10.1007","author":[{"given":"Paul","family":"Bonsma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Zickfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"7_CR1","doi-asserted-by":"publisher","first-page":"920","DOI":"10.1137\/060664318","volume":"22","author":"P. Bonsma","year":"2008","unstructured":"Bonsma, P.: Spanning trees with many leaves in graphs with minimum degree three. SIAM J. Discrete Math.\u00a022(3), 920\u2013937 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"7_CR2","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. Bonsma","year":"2008","unstructured":"Bonsma, P., Zickfeld, F.: Spanning trees with many leaves in graphs without diamonds 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)"},{"issue":"4","key":"7_CR3","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1002\/net.10097","volume":"42","author":"X. Cheng","year":"2003","unstructured":"Cheng, X., Huang, X., Li, D., Wu, W., Du, D.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks\u00a042(4), 202\u2013208 (2003)","journal-title":"Networks"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-540-77918-6_15","volume-title":"Approximation and Online Algorithms","author":"J.R. Correa","year":"2008","unstructured":"Correa, J.R., Fernandes, C.G., Matamala, M., Wakabayashi, Y.: A 5\/3-approximation for finding spanning trees with many leaves in cubic graphs. In: Kaklamanis, C., Skutella, M. (eds.) WAOA 2007. LNCS, vol.\u00a04927, pp. 184\u2013192. Springer, Heidelberg (2008)"},{"key":"7_CR5","volume-title":"Graph Theory","author":"R. Diestel","year":"1997","unstructured":"Diestel, R.: Graph Theory. Springer, New York (1997)"},{"key":"7_CR6","unstructured":"Drescher, M., Vetta, A.: An approximation algorithm for the max leaf spanning arborescence problem. ACM transactions on algorithms (to appear)"},{"key":"7_CR7","unstructured":"Estivill-Castro, V., Fellows, M.R., Langston, M.A., Rosamond, F.A.: FPT is P-time extremal structure I. In: ACiD 2005. Texts in algorithmics, vol.\u00a04, pp. 1\u201341. King\u2019s College Publications (2005)"},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/11944836_16","volume-title":"FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Solving connected dominating set faster than \n                    \n                      \n                    \n                    $2\\sp n$\n                  . In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol.\u00a04337, pp. 152\u2013163. Springer, Heidelberg (2006)"},{"issue":"1","key":"7_CR9","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0304-3975(96)00265-4","volume":"181","author":"G. Galbiati","year":"1997","unstructured":"Galbiati, G., Morzenti, A., Maffioli, F.: On the approximability of some maximum spanning tree problems. Theoret. Comput. Sci.\u00a0181(1), 107\u2013118 (1997)","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"7_CR10","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1002\/jgt.3190130604","volume":"13","author":"J.R. Griggs","year":"1989","unstructured":"Griggs, J.R., Kleitman, D.J., Shastri, A.: Spanning trees with many leaves in cubic graphs. J. Graph Theory\u00a013(6), 669\u2013695 (1989)","journal-title":"J. Graph Theory"},{"issue":"2","key":"7_CR11","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0012-365X(92)90331-9","volume":"104","author":"J.R. Griggs","year":"1992","unstructured":"Griggs, J.R., Wu, M.: Spanning trees in graphs of minimum degree 4 or 5. Discrete Math.\u00a0104(2), 167\u2013183 (1992)","journal-title":"Discrete Math."},{"issue":"4","key":"7_CR12","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S. Guha","year":"1998","unstructured":"Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica\u00a020(4), 374\u2013387 (1998)","journal-title":"Algorithmica"},{"issue":"1","key":"7_CR13","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/0404010","volume":"4","author":"D.J. Kleitman","year":"1991","unstructured":"Kleitman, D.J., West, D.B.: Spanning trees with many leaves. SIAM J. Discrete Math.\u00a04(1), 99\u2013106 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"7_CR14","unstructured":"Lemke, P.: The maximum-leaf spanning tree problem in cubic graphs is NP-complete. IMA publication no. 428, University of Minnesota, Mineapolis (1988)"},{"key":"7_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1007\/3-540-45749-6_60","volume-title":"Algorithms - ESA 2002","author":"K. Lory\u015b","year":"2002","unstructured":"Lory\u015b, K., Zwo\u017aniak, G.: Approximation algorithm for the maximum leaf spanning tree problem for cubic graphs. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 686\u2013697. Springer, Heidelberg (2002)"},{"issue":"1","key":"7_CR16","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1006\/jagm.1998.0944","volume":"29","author":"H. Lu","year":"1998","unstructured":"Lu, H., Ravi, R.: Approximating maximum leaf spanning trees in almost linear time. Journal of Algorithms\u00a029(1), 132\u2013141 (1998)","journal-title":"Journal of Algorithms"},{"issue":"1-3","key":"7_CR17","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.tcs.2004.08.013","volume":"329","author":"L. Ruan","year":"2004","unstructured":"Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.: A greedy approximation for minimum connected dominating sets. Theoret. Comput. Sci.\u00a0329(1-3), 325\u2013330 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"7_CR19","unstructured":"Zickfeld, F.: Geometric and combinatorial structures on graphs. PhD thesis, Technische Universit\u00e4t Berlin, Berlin (2007)"}],"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-540-92248-3_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,4]],"date-time":"2019-03-04T08:05:58Z","timestamp":1551686758000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92248-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540922476","9783540922483"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92248-3_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}