Approximating degree-bounded minimum spanning trees of directed acyclic graphs

作     者：Li, Hengwu Liu, Zhendong Han, Huijian 

作者机构：Department of Computer Science and Technology Shandong Economic University Jinan 250014 China Department of Computer Science and Technology Shandong Architecture University Jinan 250101 China 

出 版 物：《Journal of Computational Information Systems》 (J. Comput. Inf. Syst.)

年 卷 期：2010年第6卷第7期

页      面：2399-2406页

核心收录：

主　　题：Approximation algorithms 

摘      要：In this paper, we present a primal-dual algorithm for the degree-bounded minimum spanning tree problem in directed acyclic graphs: Given a directed acyclic graph G = (V, E) with nonnegative edge costs ce for all e ∈ E and integer degree bounds Bv ≥ 1 for all v ∈ V and a root vertex r ∈ V, find a minimum-cost spanning tree T rooted at r such that the degree of each vertex v in T is at most Bv. Approximation algorithms are known for the undirected version of the problem, but none for the directed version to our knowledge. Our algorithm goes through a series of spanning trees and improves the maximum deviation of any vertex degree from its respective degree bound iteratively. The algorithm output a tree in which the degree of each vertex v is O(Bv + log n) and the total cost is at most a constant times the cost of any tree rooted at r that obeys all degree constraints. Copyright © 2010 Binary Information Press.