Near-linear Time Algorithm for Approximate Minimum Degree Spanning Trees

Ran Duan, Haoqing He, Tianyi Zhang

Given a graph $G=(V,E)$, we wish to compute a spanning tree whose maximum vertex degree, i.e. tree degree, is as small as possible. Computing the exact optimal solution is known…