{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:36:44Z","timestamp":1770921404033,"version":"3.50.1"},"publisher-location":"Cham","reference-count":21,"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_23","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:12Z","timestamp":1770918792000},"page":"303-316","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Finding a\u00a0HIST: Chordality, Structural Parameters, and\u00a0Diameter"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6943-856X","authenticated-orcid":false,"given":"Tesshu","family":"Hanaka","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0742-4477","authenticated-orcid":false,"given":"Hironori","family":"Kiya","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0845-3947","authenticated-orcid":false,"given":"Hirotaka","family":"Ono","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"issue":"2","key":"23_CR1","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1002\/jgt.3190140212","volume":"14","author":"MO Albertson","year":"1990","unstructured":"Albertson, M.O., Berman, D.M., Hutchinson, J.P., Thomassen, C.: Graphs with homeomorphically irreducible spanning trees. J. Graph Theory 14(2), 247\u2013258 (1990)","journal-title":"J. Graph Theory"},{"issue":"2","key":"23_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"23_CR3","unstructured":"Bachtler, O.: On Algorithmic Certification of Graph Structures. doctoralthesis, Rheinland-Pf\u00e4lzische Technische Universit\u00e4t Kaiserslautern-Landau (2023)"},{"issue":"4","key":"23_CR4","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1016\/j.jctb.2013.04.001","volume":"103","author":"G Chen","year":"2013","unstructured":"Chen, G., Shan, S.: Homeomorphically irreducible spanning trees. J. Comb. Theory B 103(4), 409\u2013414 (2013)","journal-title":"J. Comb. Theory B"},{"issue":"1\u20132","key":"23_CR5","first-page":"1","volume":"21","author":"J Cong","year":"1996","unstructured":"Cong, J., He, L., Koh, C., Madden, P.H.: Performance optimization of VLSI interconnect layout. Integr. 21(1\u20132), 1\u201394 (1996)","journal-title":"Integr."},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: On the expression of graph properties in some fragments of monadic second-order logic. In: Immerman, N., Kolaitis, P.G. (eds.) Descriptive Complexity and Finite Models, Proceedings of a DIMACS Workshop 1996, Princeton, New Jersey, USA, 14\u201317 January 1996. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a031, pp. 33\u201362. DIMACS\/AMS (1996)","DOI":"10.1090\/dimacs\/031\/02"},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.dam.2014.12.023","volume":"185","author":"J Diemunsch","year":"2015","unstructured":"Diemunsch, J., et al.: A characterization of $$P_5$$-free graphs with a homeomorphically irreducible spanning tree. Discret. Appl. Math. 185, 71\u201378 (2015)","journal-title":"Discret. Appl. Math."},{"issue":"1\u20133","key":"23_CR9","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(92)90130-8","volume":"105","author":"RJ Douglas","year":"1992","unstructured":"Douglas, R.J.: NP-completeness and degree restricted spanning trees. Discret. Math. 105(1\u20133), 41\u201347 (1992)","journal-title":"Discret. Math."},{"issue":"2","key":"23_CR10","doi-asserted-by":"publisher","first-page":"114307","DOI":"10.1016\/j.disc.2024.114307","volume":"348","author":"M Furuya","year":"2025","unstructured":"Furuya, M., Saito, A., Tsuchiya, S.: Refinements of degree conditions for the existence of a spanning tree without small degree stems. Discret. Math. 348(2), 114307 (2025)","journal-title":"Discret. Math."},{"issue":"2","key":"23_CR11","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180\u2013187 (1972)","journal-title":"SIAM J. Comput."},{"key":"23_CR12","unstructured":"Hanaka, T., Kiya, H., Ono, H.: Finding a hist: Chordality, structural parameters, and diameter (2025). https:\/\/arxiv.org\/abs\/2510.04418"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"115092","DOI":"10.1016\/j.tcs.2025.115092","volume":"1033","author":"T Hanaka","year":"2025","unstructured":"Hanaka, T., Kobayashi, Y.: Finding a minimum spanning tree with a small non-terminal set. Theor. Comput. Sci. 1033, 115092 (2025)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"Hill, A.: Graphs with homeomorphically irreducible spanning trees. In: Combinatorics (Proceedings of British Combinatorial Conference, University of College Wales, Aberystwyth, 1973), pp. 61\u201368 (1974)","DOI":"10.1017\/CBO9780511662072.011"},{"key":"23_CR15","unstructured":"Hoffmann-Ostenhof, A.: Nowhere-Zero Flows and Structures in Cubic Graphs. Ph.D. thesis, University of Vienna (2011)"},{"issue":"1\u20133","key":"23_CR16","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0012-365X(94)90118-X","volume":"128","author":"D Kratsch","year":"1994","unstructured":"Kratsch, D., Damaschke, P., Lubiw, A.: Dominating cliques in chordal graphs. Discret. Math. 128(1\u20133), 269\u2013275 (1994)","journal-title":"Discret. Math."},{"issue":"1","key":"23_CR17","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1111\/j.1749-6632.1979.tb32810.x","volume":"319","author":"J Malkevitch","year":"1979","unstructured":"Malkevitch, J.: Spanning trees in polytopal graphs. Ann. N. Y. Acad. Sci. 319(1), 362\u2013367 (1979)","journal-title":"Ann. N. Y. Acad. Sci."},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"de\u00a0Melo, A.A., de\u00a0Figueiredo, C.M.H., Souza, U.S.: On the terminal connection problem. In: Bures, T., et al. (eds.) SOFSEM 2021: Theory and Practice of Computer Science - 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Bolzano-Bozen, Italy, 25\u201329 January 2021, Proceedings. LNCS, vol. 12607, pp. 278\u2013292. Springer (2021)","DOI":"10.1007\/978-3-030-67731-2_20"},{"issue":"4","key":"23_CR19","doi-asserted-by":"publisher","first-page":"886","DOI":"10.1002\/jgt.23005","volume":"104","author":"S Shan","year":"2023","unstructured":"Shan, S., Tsuchiya, S.: Characterization of graphs of diameter 2 containing a homeomorphically irreducible spanning tree. J. Graph Theory 104(4), 886\u2013903 (2023)","journal-title":"J. Graph Theory"},{"key":"23_CR20","unstructured":"Tran, D.L.: Expanding the graph parameter hierarchy. Bachelor thesis, Technische Universit\u00e4t Berlin, Institute of Software Engineering and Theoretical Computer Science (AKT), September 2022, https:\/\/fpt.akt.tu-berlin.de\/publications\/theses\/BA-Duc-Long-Tran.pdf, supervisor: Dr. Andr\u00e9 Nichterlein; Second reviewer: Prof. Dr. Stephan Kreutzer"},{"key":"23_CR21","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.tre.2017.11.001","volume":"109","author":"M Zhalechian","year":"2018","unstructured":"Zhalechian, M., Torabi, S.A., Mohammadi, M.: Hub-and-spoke network design under operational and disruption risks. Transp. Res. Part E: Logist. Transp. Rev. 109, 20\u201343 (2018)","journal-title":"Transp. Res. Part E: Logist. Transp. Rev."}],"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_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:16Z","timestamp":1770918796000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_23","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"}}]}}