15 citations · 41 across the 17 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.DS2017
Near-linear Time Algorithm for Approximate Minimum Degree Spanning Trees
Ran Duan, Haoqing He, Tianyi Zhang
Given a graph , 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…
cs.DS2017
Purely Combinatorial Algorithms for Approximate Directed Minimum Degree Spanning Trees
Ran Duan, Tianyi Zhang
Given a directed graph on vertices with a special vertex , the directed minimum degree spanning tree problem requires computing a incoming spanning tree rooted at wh…