Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5775581 | Applied Mathematics and Computation | 2018 | 7 Pages |
Abstract
This paper studies approximation algorithm for the degree-balanced spanning tree (DBST) problem. Given a graph G=(V,E), the goal is to find a spanning tree T such that âvâ¯ââ¯VdegT(v)2 is minimized, where degT(v) denotes the degree of node v in tree T. The idea of taking squares on node degrees is to manifest the role of nodes with large degree, and thus minimizing the sum will result in a comparatively balanced degree distribution. This is a non-linear objective function. We prove that DBST is NP-hard, and then develop a primal-dual based algorithm with a guaranteed performance ratio.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Yingli Ran, Zhihao Chen, Shaojie Tang, Zhao Zhang,