{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:37:05Z","timestamp":1770921425588,"version":"3.50.1"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-17801-5_42","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:35Z","timestamp":1770918815000},"page":"578-592","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Spanning Trees with\u00a0a\u00a0Small Vertex Cover: The\u00a0Complexity on\u00a0Specific Graph Classes"],"prefix":"10.1007","author":[{"given":"Toranosuke","family":"Kokai","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5212-0202","authenticated-orcid":false,"given":"Akira","family":"Suzuki","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0005-8433-3789","authenticated-orcid":false,"given":"Takahiro","family":"Suzuki","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0001-5479-7006","authenticated-orcid":false,"given":"Yuma","family":"Tamura","sequence":"additional","affiliation":[]},{"given":"Xiao","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"42_CR1","doi-asserted-by":"publisher","unstructured":"Angel, E., Bampis, E., Chau, V., Kononov, A.V.: Min-power covering problems. In: Elbassioni, K.M., Makino, K., (eds.) Algorithms and Computation - 26th International Symposium, ISAAC 2015, volume 9472 of Lecture Notes in Computer Science, pp. 367\u2013377. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-662-48971-0_32","DOI":"10.1007\/978-3-662-48971-0_32"},{"key":"42_CR2","doi-asserted-by":"publisher","unstructured":"Mark de Berg and Amirali Khosravi. Optimal binary space partitions in the plane. In: Thai, M.T., Sahni, S., (eds.) Computing and Combinatorics, 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19\u201321, 2010. Proceedings, volume 6196 of Lecture Notes in Computer Science, pp. 216\u2013225. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-14031-0_25","DOI":"10.1007\/978-3-642-14031-0_25"},{"issue":"2","key":"42_CR3","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1137\/S0895480199353780","volume":"13","author":"Y Caro","year":"2000","unstructured":"Caro, Y., West, D.B., Yuster, R.: Connected domination and spanning trees with many leaves. SIAM J. Discret. Math. 13(2), 202\u2013211 (2000). https:\/\/doi.org\/10.1137\/S0895480199353780","journal-title":"SIAM J. Discret. Math."},{"issue":"11","key":"42_CR4","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1016\/J.IC.2008.07.003","volume":"206","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput. 206(11), 1264\u20131275 (2008). https:\/\/doi.org\/10.1016\/J.IC.2008.07.003","journal-title":"Inf. Comput."},{"issue":"2","key":"42_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/S002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000). https:\/\/doi.org\/10.1007\/S002249910009","journal-title":"Theory Comput. Syst."},{"issue":"06","key":"42_CR6","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1142\/S0129054118500168","volume":"29","author":"A Darmann","year":"2018","unstructured":"Darmann, A., D\u00f6cker, J., Dorn, B.: The monotone satisfiability problem with bounded variable appearances. Int. J. Found. Comput. Sci. 29(06), 979\u2013993 (2018). https:\/\/doi.org\/10.1142\/S0129054118500168","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"42_CR7","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1007\/S00224-009-9167-9","volume":"45","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., et al.: The complexity ecology of parameters: an illustration using bounded max leaf number. Theory Comput. Syst. 45(4), 822\u2013848 (2009). https:\/\/doi.org\/10.1007\/S00224-009-9167-9","journal-title":"Theory Comput. Syst."},{"issue":"1\u20133","key":"42_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/J.APAL.2004.01.007","volume":"130","author":"M Frick","year":"2004","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Log. 130(1\u20133), 3\u201331 (2004). https:\/\/doi.org\/10.1016\/J.APAL.2004.01.007","journal-title":"Ann. Pure Appl. Log."},{"key":"42_CR9","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/J.TCS.2019.05.018","volume":"791","author":"T Fukunaga","year":"2019","unstructured":"Fukunaga, T., Maehara, T.: Computing a tree having a small vertex cover. Theor. Comput. Sci. 791, 48\u201361 (2019). https:\/\/doi.org\/10.1016\/J.TCS.2019.05.018","journal-title":"Theor. Comput. Sci."},{"key":"42_CR10","doi-asserted-by":"publisher","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423\u2013443 (2000). https:\/\/doi.org\/10.1142\/S0129054100000260","DOI":"10.1142\/S0129054100000260"},{"key":"42_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-540-75520-3_16","volume-title":"Algorithms \u2013 ESA 2007","author":"P Hlin\u011bn\u00fd","year":"2007","unstructured":"Hlin\u011bn\u00fd, P., Oum, S.: Finding branch-decompositions and rank-decompositions. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 163\u2013174. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-75520-3_16"},{"key":"42_CR12","doi-asserted-by":"publisher","unstructured":"Ho, J., Lee, D.T., Chang, C., Wong, C.K.: Minimum diameter spanning trees and related problems. SIAM J. Comput. 20(5), 987\u2013997 (1991). https:\/\/doi.org\/10.1137\/0220060","DOI":"10.1137\/0220060"},{"issue":"3","key":"42_CR13","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/S0097539792224814","volume":"28","author":"WL Hsu","year":"1999","unstructured":"Hsu, W.L., Ma, T.H.: Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs. SIAM J. Comput. 28(3), 1004\u20131020 (1999). https:\/\/doi.org\/10.1137\/S0097539792224814","journal-title":"SIAM J. Comput."},{"key":"42_CR14","doi-asserted-by":"publisher","unstructured":"Kaur, C., Misra, N.: On the parameterized complexity of spanning trees with small vertex covers. In Changat, M., Das, S., (eds.) Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, volume 12016 of Lecture Notes in Computer Science, pp. 427\u2013438. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-39219-2_34","DOI":"10.1007\/978-3-030-39219-2_34"},{"key":"42_CR15","doi-asserted-by":"publisher","unstructured":"Keil, J.M., Belleville, P.: Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs. Discrete Applied Math. 140(1), 73\u201389 (2004). https:\/\/doi.org\/10.1016\/j.dam.2003.04.004","DOI":"10.1016\/j.dam.2003.04.004"},{"key":"42_CR16","unstructured":"Kokai, T., Suzuki, A., Suzuki, T., Tamura, Y., Zhou, X.: Spanning trees with a small vertex cover: the complexity on specific graph classes (2025). https:\/\/arxiv.org\/abs\/2511.22912"},{"issue":"3","key":"42_CR17","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1137\/0406032","volume":"6","author":"D Kratsch","year":"1993","unstructured":"Kratsch, D., Stewart, L.: Domination on cocomparability graphs. SIAM J. Discret. Math. 6(3), 400\u2013417 (1993). https:\/\/doi.org\/10.1137\/0406032","journal-title":"SIAM J. Discret. Math."},{"key":"42_CR18","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Misra, N., Philip, G., Ramanujan, M.S., Saurabh, S.: Hardness of $$r$$-dominating set on graphs of diameter $$(r + 1)$$. In: Gutin, G.Z., Szeider, S., (eds.) Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, volume 8246 of Lecture Notes in Computer Science, pp. 255\u2013267. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_22","DOI":"10.1007\/978-3-319-03898-8_22"},{"key":"42_CR19","doi-asserted-by":"crossref","unstructured":"Oum, S.: Approximating rank-width and clique-width quickly. In: Kratsch, D., (ed.) Graph-Theoretic Concepts in Computer Science, pp. 49\u201358, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg","DOI":"10.1007\/11604686_5"},{"key":"42_CR20","doi-asserted-by":"publisher","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Combinatorial Theor. Ser. B 96(4), 514\u2013528 (2006). https:\/\/doi.org\/10.1016\/j.jctb.2005.10.006","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"42_CR21","doi-asserted-by":"publisher","unstructured":"Ravi, R.: Rapid rumor ramification: approximating the minimum broadcast time (extended abstract). In: 35th Annual Symposium on Foundations of Computer Science, pp. 202\u2013213. IEEE Computer Society, 1994. https:\/\/doi.org\/10.1109\/SFCS.1994.365693","DOI":"10.1109\/SFCS.1994.365693"},{"key":"42_CR22","doi-asserted-by":"publisher","unstructured":"Rosamond, F.A.: Max leaf spanning tree. In: Kao, M., (ed.) Encyclopedia of Algorithms, pp. 1211\u20131215. Springer (2016). https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_228","DOI":"10.1007\/978-1-4939-2864-4_228"},{"issue":"5","key":"42_CR23","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/J.IPL.2007.08.030","volume":"105","author":"G Salamon","year":"2008","unstructured":"Salamon, G., Wiener, G.: On finding spanning trees with few leaves. Inf. Process. Lett. 105(5), 164\u2013169 (2008). https:\/\/doi.org\/10.1016\/J.IPL.2007.08.030","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"42_CR24","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"30","author":"LG Valiant","year":"1981","unstructured":"Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Comput. 30(2), 135\u2013140 (1981)","journal-title":"IEEE Trans. Comput."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:37Z","timestamp":1770918817000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}