Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier

Proceedings of the 58th Annual ACM Symposium on Theory of Computing 2026 Open access

Read full text
Authors: Sayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang
DOI: 10.1145/3798129.3800832
Cited by: 1
References: 11

Abstract

We consider the “minimum degree spanning tree” problem. As input, we receive an undirected, connected graph G=(V, E) with n nodes and m edges, and our task is to find a spanning tree T of G that minimizes maxu ∈ V degT(u), where degT(u) denotes the degree of u ∈ V in T.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Distributed systems and fault tolerance Advanced Graph Theory Research

Publication details

Journal / source
Proceedings of the 58th Annual ACM Symposium on Theory of Computing
Publisher
ACM
Pages
1212–1223
Publication date
9 June 2026