کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649540 1342459 2008 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
چکیده انگلیسی

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn)O(mnlogn) time, where m and n   are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of O(logn/logOPT) of the optimum in O(mnlogn)O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ*/logΔ*)O(Δ*/logΔ*) of the optimum in O(mnlogn)O(mnlogn)-time, where Δ*Δ* is the minimum k such that there is a spanning tree of the graph with maximum degree k.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 17, 6 September 2008, Pages 3951–3959
نویسندگان
, , , ,