{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T20:52:11Z","timestamp":1742935931516,"version":"3.40.3"},"publisher-location":"Cham","reference-count":14,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031630200"},{"type":"electronic","value":"9783031630217"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-63021-7_38","type":"book-chapter","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T13:02:29Z","timestamp":1718974949000},"page":"497-508","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Spanning Tree Congestion on\u00a0Graphs with\u00a0Polylog Degree"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2235-0506","authenticated-orcid":false,"given":"Petr","family":"Kolman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,22]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2), 5:1\u20135:37 (2009). Preliminary version in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC) (2004)","DOI":"10.1145\/1502793.1502794"},{"issue":"1","key":"38_CR2","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s00453-011-9565-7","volume":"64","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender, H.L., Fomin, F.V., Golovach, P.A., Otachi, Y., van Leeuwen, E.J.: Parameterized complexity of the spanning tree congestion problem. Algorithmica 64(1), 85\u2013111 (2012)","journal-title":"Algorithmica"},{"key":"38_CR3","unstructured":"Bor\u016fvka, O.: O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm (About a certain minimal problem). Pr\u00e1ce Moravsk\u00e9 p\u0159\u00edrodov\u011bdeck\u00e9 spole\u010dnosti III(3), 37\u201358 (1926)"},{"issue":"4","key":"38_CR4","doi-asserted-by":"publisher","first-page":"1090","DOI":"10.1137\/S0097539701387660","volume":"31","author":"U Feige","year":"2002","unstructured":"Feige, U., Krauthgamer, R.: A polylogarithmic approximation of the minimum bisection. SIAM J. Comput. 31(4), 1090\u20131118 (2002)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"38_CR5","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1002\/jgt.22248","volume":"89","author":"CG Fernandes","year":"2018","unstructured":"Fernandes, C.G., Schmidt, T.J., Taraz, A.: On minimum bisection and related cut problems in trees and tree-like graphs. J. Graph Theory 89(2), 214\u2013245 (2018)","journal-title":"J. Graph Theory"},{"key":"38_CR6","first-page":"18","volume":"58","author":"H-F Law","year":"2010","unstructured":"Law, H.-F., Ostrovskii, M.: Spanning tree congestion: duality and isoperimetry; with an application to multipartite graphs. Graph Theory Notes New York 58, 18\u201326 (2010)","journal-title":"Graph Theory Notes New York"},{"key":"38_CR7","unstructured":"L\u00f6wenstein, C.: In the complement of a dominating set. Ph.D. thesis, TU Ilmenau (2010)"},{"key":"38_CR8","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-031-27051-2_15","volume-title":"WALCOM 2023","author":"H Luu","year":"2023","unstructured":"Luu, H., Chrobak, M.: Better hardness results for the minimum spanning tree congestion problem. In: Lin, C.C., Lin, B.M.T., Liotta, G. (eds.) WALCOM 2023. LNCS, vol. 13973, pp. 167\u2013178. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-27051-2_15"},{"issue":"6","key":"38_CR9","doi-asserted-by":"publisher","first-page":"727","DOI":"10.7155\/jgaa.00246","volume":"15","author":"Y Okamoto","year":"2011","unstructured":"Okamoto, Y., Otachi, Y., Uehara, R., Uno, T.: Hardness results and an exact exponential algorithm for the spanning tree congestion problem. J. Graph Algorithms Appl. 15(6), 727\u2013751 (2011)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"38_CR10","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.disc.2004.02.009","volume":"285","author":"M Ostrovskii","year":"2004","unstructured":"Ostrovskii, M.: Minimal congestion trees. Discret. Math. 285(1), 219\u2013226 (2004)","journal-title":"Discret. Math."},{"key":"38_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-030-42071-0_12","volume-title":"Treewidth, Kernels, and Algorithms","author":"Y Otachi","year":"2020","unstructured":"Otachi, Y.: A survey on spanning tree congestion. In: Fomin, F.V., Kratsch, S., van Leeuwen, E.J. (eds.) Treewidth, Kernels, and Algorithms. LNCS, vol. 12160, pp. 165\u2013172. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-42071-0_12"},{"key":"38_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-642-16926-7_3","volume-title":"Graph Theoretic Concepts in Computer Science","author":"Y Otachi","year":"2010","unstructured":"Otachi, Y., Bodlaender, H.L., van Leeuwen, E.J.: Complexity results for the spanning tree congestion problem. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol. 6410, pp. 3\u201314. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16926-7_3"},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 255\u2013264. ACM (2008)","DOI":"10.1145\/1374376.1374415"},{"issue":"4","key":"38_CR14","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BF01692067","volume":"20","author":"S Simonson","year":"1987","unstructured":"Simonson, S.: A variation on the min cut linear arrangement problem. Math. Syst. Theory 20(4), 235\u2013252 (1987)","journal-title":"Math. Syst. Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-63021-7_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T13:18:46Z","timestamp":1718975926000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-63021-7_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031630200","9783031630217"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-63021-7_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"22 June 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ischia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"35","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/iwoca2024.di.unisa.it","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}