{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:28Z","timestamp":1781031448276,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":14,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"ERC","award":["101170133"],"award-info":[{"award-number":["101170133"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800832","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1212-1223","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1612-0296","authenticated-orcid":false,"given":"Sayan","family":"Bhattacharya","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-6529-8625","authenticated-orcid":false,"given":"Ermiya","family":"Farokhnejad","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-3195-9083","authenticated-orcid":false,"given":"Haoze","family":"Wang","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Sayan Bhattacharya Ermiya Farokhnejad and Haoze Wang. 2026. Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier. arxiv:2602.23448"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","unstructured":"Kamalika Chaudhuri Satish Rao Samantha J. Riesenfeld and Kunal Talwar. 2005. What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs. In Approximation Randomization and Combinatorial Optimization Algorithms and Techniques 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation RANDOM 2005 Berkeley CA USA August 22-24 2005 Proceedings Chandra Chekuri Klaus Jansen Jos\u00e9 D. P. Rolim and Luca Trevisan (Eds.) (Lecture Notes in Computer Science Vol. 3624). Springer 26\u201339. https:\/\/doi.org\/10.1007\/11538462_3 10.1007\/11538462_3","DOI":"10.1007\/11538462_3"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2021.24"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-61792-9_2"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1146610"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/139404.139469"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.48"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335371"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977152"},{"key":"e_1_3_2_1_10_1","unstructured":"Seth Pettie. 2016. Open Problem 24: Hardness of Approximating NP-hard Problems. Dagstuhl Seminar 16451: Structure and Hardness in P."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167209"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/DagRep.14.11.92"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250887"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800832","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:03:04Z","timestamp":1781028184000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800832"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":14,"alternative-id":["10.1145\/3798129.3800832","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800832","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}