{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T15:07:30Z","timestamp":1767193650355,"version":"3.48.0"},"reference-count":6,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T00:00:00Z","timestamp":1761350400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T00:00:00Z","timestamp":1761350400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100002418","name":"Intel Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100002418","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2018\/31\/B\/ST6\/00820"],"award-info":[{"award-number":["2018\/31\/B\/ST6\/00820"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We present a simple linear-time algorithm that finds a spanning tree\n                    <jats:italic>T<\/jats:italic>\n                    of a given 2-edge-connected graph\n                    <jats:italic>G<\/jats:italic>\n                    such that each vertex\n                    <jats:italic>v<\/jats:italic>\n                    of\n                    <jats:italic>T<\/jats:italic>\n                    has degree at most\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\lceil \\frac{\\deg _G(v)}{2}\\rceil + 1$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>","DOI":"10.1007\/s10878-025-01368-2","type":"journal-article","created":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T07:19:12Z","timestamp":1761376752000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Low-degree spanning trees of 2-edge-connected graphs in linear time"],"prefix":"10.1007","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4000-4818","authenticated-orcid":false,"given":"Dariusz","family":"Dereniowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2575-4373","authenticated-orcid":false,"given":"Janusz","family":"Dybizba\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Przemys\u0142aw","family":"Karpi\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4845-7707","authenticated-orcid":false,"given":"Micha\u0142","family":"Zakrzewski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6378-7742","authenticated-orcid":false,"given":"Pawe\u0142","family":"\u017byli\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,25]]},"reference":[{"issue":"4","key":"1368_CR1","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1002\/jgt.10092","volume":"42","author":"J Bang-Jensen","year":"2003","unstructured":"Bang-Jensen J, Thomass\u00e9 S, Yeo A (2003) Small degree out-branchings. J Graph Theory 42(4):297\u2013307","journal-title":"J Graph Theory"},{"key":"1368_CR2","doi-asserted-by":"crossref","unstructured":"Chartrand G, Jordon H, Vatter V, Zhang P (2024) Graphs and digraphs. 7th Edition. Chapman & Hall","DOI":"10.1201\/9781003461289"},{"key":"1368_CR3","doi-asserted-by":"crossref","unstructured":"Czumaj A, Strothmann WB (1997) Bounded degree spanning trees. In: 5th Annual European symposium on algorithms ESA 97, volume 1284 of Lecture Notes in Computer Science, pp 104\u2013117. Springer","DOI":"10.1007\/3-540-63397-9_9"},{"issue":"8","key":"1368_CR4","doi-asserted-by":"publisher","first-page":"1317","DOI":"10.1016\/j.disc.2015.02.022","volume":"338","author":"M Hasanvand","year":"2015","unstructured":"Hasanvand M (2015) Spanning trees and spanning Eulerian subgraphs with small degrees. Discrete Math 338(8):1317\u20131321","journal-title":"Discrete Math"},{"issue":"2","key":"1368_CR5","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1002\/(SICI)1097-0118(199806)28:2<87::AID-JGT2>3.0.CO;2-A","volume":"28","author":"Z Liu","year":"1998","unstructured":"Liu Z, Baoguang X (1998) On low bound of degree sequences of spanning trees in K-edge-connected graphs. J Graph Theory 28(2):87\u201395","journal-title":"J Graph Theory"},{"issue":"4","key":"1368_CR6","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1002\/jgt.20311","volume":"58","author":"C Thomassen","year":"2008","unstructured":"Thomassen C (2008) Decompositions of highly connected graphs into paths of length 3. J Graph Theory 58(4):286\u2013292","journal-title":"J Graph Theory"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01368-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01368-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01368-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T15:03:17Z","timestamp":1767193397000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01368-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,25]]},"references-count":6,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["1368"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01368-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2025,10,25]]},"assertion":[{"value":"26 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"36"}}