{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T23:30:31Z","timestamp":1794353431318,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540779179","type":"print"},{"value":"9783540779186","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77918-6_15","type":"book-chapter","created":{"date-parts":[[2008,2,8]],"date-time":"2008-02-08T03:41:19Z","timestamp":1202442079000},"page":"184-192","source":"Crossref","is-referenced-by-count":7,"title":["A 5\/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs"],"prefix":"10.1007","author":[{"given":"Jos\u00e9 R.","family":"Correa","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cristina G.","family":"Fernandes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mart\u00edn","family":"Matamala","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yoshiko","family":"Wakabayashi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"15_CR1","unstructured":"Bonsma, P.: Spanning trees with many leaves: new extremal results and an improved FPT algorithm. Technical report, Faculty of EEMCS, University of Twente, The Netherlands (2006)"},{"issue":"1","key":"15_CR2","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0020-0190(94)90139-2","volume":"52","author":"G. Galbiati","year":"1994","unstructured":"Galbiati, G., Maffioli, F., Morzenti, A.: A short note on the approximability of the maximum leaves spanning tree problem. Information Processing Letters\u00a052(1), 45\u201349 (1994)","journal-title":"Information Processing Letters"},{"key":"15_CR3","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"issue":"6","key":"15_CR4","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1002\/jgt.3190130604","volume":"13","author":"J. Griggs","year":"1989","unstructured":"Griggs, J., Kleitman, D., Shastri, A.: Spanning trees with many leaves in cubic graphs. Journal of Graph Theory\u00a013(6), 669\u2013695 (1989)","journal-title":"Journal of Graph Theory"},{"issue":"1","key":"15_CR5","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/0404010","volume":"4","author":"D. Kleitman","year":"1991","unstructured":"Kleitman, D., West, D.: Spanning trees with many leaves. SIAM Journal on Discrete Mathematics\u00a04(1), 99\u2013106 (1991)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"15_CR6","unstructured":"Lemke, P.: The maximum-leaf spanning tree problem in cubic graphs is NP-complete. In: IMA Preprint Series 428, Mineapolis (1988)"},{"key":"15_CR7","unstructured":"SLinial, N., Sturtevant, D.: Private communication (1987) (see [5])"},{"key":"15_CR8","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","year":"2002","unstructured":"Lory, K., Zwo\u017aniak, G.: Approximation algorithm for maximum leaf spanning tree problem for cubic graphs. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 686\u2013698. Springer, Heidelberg (2002)"},{"key":"15_CR9","unstructured":"Lu, H.I., Ravi, R.: The power of local optimization: Approximation algorithms for maximum-leaf spanning tree. In: Proceedings of 13th Annual Allerton Conference on Communication, Control, and Computing, pp. 533\u2013542 (1992)"},{"issue":"1","key":"15_CR10","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(1), 132\u2013141 (1998)","journal-title":"Journal of Algorithms"},{"key":"15_CR11","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)"},{"issue":"1","key":"15_CR12","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/0020-0190(81)90141-1","volume":"13","author":"J. Storer","year":"1981","unstructured":"Storer, J.: Constructing full spanning trees for cubic graphs. Information Processing Letters\u00a013(1), 8\u201311 (1981)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77918-6_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:56:14Z","timestamp":1619506574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77918-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540779179","9783540779186"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77918-6_15","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-540-77918-6","asserted-by":"object"}]},"subject":[]}}