Spanning trees with minimum weighted degrees |
| |
Authors: | Mohammad Ghodsi Hamid Mahini Kian Mirjalali |
| |
Affiliation: | a Department of Computer Engineering, Sharif University of Technology, Tehran, Iran b School of Computer Science, Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran |
| |
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. |
| |
Keywords: | Approximation algorithms Graph algorithms Spanning trees |
本文献已被 ScienceDirect 等数据库收录! |
|