Name
Abstract | ||
|---|---|---|
Given a metric graph G, we are concerned with finding a spanning tree of G where the maximum weighted degree of its vertices is minimum. In a metric graph (or its spanning tree), the weighted degree of a vertex is defined as the sum of the weights of its incident edges. In this paper, we propose a 4.5-approximation algorithm for this problem. We also prove it is NP-hard to approximate this problem within a 2-ε factor. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.ipl.2007.06.011 | Inf. Process. Lett. |
Keywords | Field | DocType |
graph algorithms,weighted degree,approximation algorithms,spanning tree,incident edge,maximum weighted degree,metric graph,spanning trees,minimum weighted degree | Discrete mathematics,Combinatorics,Minimum degree spanning tree,Prim's algorithm,Euclidean minimum spanning tree,Degree (graph theory),Spanning tree,Reverse-delete algorithm,Kruskal's algorithm,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
104 | 3 | 0020-0190 |
Citations | PageRank | References |
1 | 0.36 | 9 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mohammad Ghodsi | 1 | 330 | 49.27 |
| Hamid Mahini | 2 | 172 | 15.10 |
| Kian Mirjalali | 3 | 1 | 0.36 |
| Shayan Oveis Gharan | 4 | 323 | 26.63 |
| Amin S. Sayedi R. | 5 | 1 | 0.36 |
| Morteza Zadimoghaddam | 6 | 382 | 34.40 |