Name
Abstract | ||
|---|---|---|
This paper addresses the Inner-node Weighted Minimum Spanning Tree Problem (IWMST), which asks for a spanning tree in a graph G = (V. E) (vertical bar V vertical bar = n. vertical bar E vertical bar = m) with the minimum total cost for its edges and non-leaf nodes. This problem is NP-Hard because it contains the connected dominating set problem (CDS) as a special case. Since CDS cannot be approximated with a factor of (1 E)H(A) (A is the maximum degree) unless NP subset of DT I M E/n(O(log log n)) vertical bar [10], we can only expect a poly-logarithmic approximation algorithm for the IWMST problem. To tackle this problem, we first present a general framework for developing poly-logarithmic approximation algorithms. Our framework aims to find a r. rk Inn-approximate Algorithm (k epsilon N and k >= 2) for the IWMST problem. Based on this framework, we further design two polynomial time approximation algorithms. The first one can find a k/k-1 In n-approximate solution in O(mn log n) time, while the second one can compute a 1.5 Inn-approximate solution in O(n(2) Delta(6)) time (Delta is the maximum degree in G). We have also studied the relationships between the IWMST problem and several other similar problems. |
Year | DOI | Venue |
|---|---|---|
2009 | null | COMPUTER SYSTEMS SCIENCE AND ENGINEERING |
Keywords | Field | DocType |
Approximation Algorithms,Inner-node Weighted Minimum Spanning Trees | Approximation algorithm,Discrete mathematics,Minimum degree spanning tree,Computer science,Spanning tree,Reverse-delete algorithm,Minimum spanning tree,Distributed computing | Journal |
Volume | Issue | ISSN |
24 | 3 | 0267-6192 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chao Peng | 1 | 23 | 5.22 |
| Yasuo Tan | 2 | 151 | 25.41 |
| Naixue Xiong | 3 | 2413 | 194.61 |
| Laurence Tianruo Yang | 4 | 10 | 1.71 |
| Hong Zhu | 5 | 179 | 23.67 |