کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437457 690144 2016 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Constructing minimum changeover cost arborescenses in bounded treewidth graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Constructing minimum changeover cost arborescenses in bounded treewidth graphs
چکیده انگلیسی

Given an edge-colored graph, an internal vertex of a path experiences a reload cost if it lies between two consecutive edges of different colors. The value of the reload cost depends only on the colors of the traversed edges. The reload cost concept has important applications in dynamic networks, such as transportation networks and dynamic spectrum access networks. In the minimum changeover cost arborescence (MinCCA) problem, we seek a spanning tree of an edge-colored graph, in which the sum of reload costs of all internal vertices, starting from a given root, is minimized. In general, MinCCA is known to be hard to approximate within factor n1−ϵn1−ϵ, for any ϵ>0ϵ>0, on a graph of n vertices.We first show that MinCCA can be optimally solved in polynomial-time on cactus graphs. Our main result is an optimal polynomial-time algorithm for graphs of bounded treewidth, thus establishing the solvability of our problem on a fundamental subclass of graphs. Our results imply that MinCCA is fixed parameter tractable when parameterized by treewidth and the maximum degree of the input graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 621, 28 March 2016, Pages 22–36
نویسندگان
, , , ,