کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431692 | 688613 | 2008 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Inapproximability and approximability of minimal tree routing and coloring Inapproximability and approximability of minimal tree routing and coloring](/preview/png/431692.png)
Let G be an undirected connected graph. Given a set of g groups each being a subset of V(G)V(G), the tree routing and coloring problem is to produce g trees in G and assign a color to each of them in such a way that all vertices in every group are connected by one of produced trees and no two trees sharing a common edge are assigned the same color. In this paper we study the problem of finding a tree routing and coloring that uses minimal number of colors in the solution. This problem has applications of multicast connections in optical networks.We first prove Ω(g1−ε)Ω(g1−ε)-inapproximability even when G is a mesh, and then we propose some approximation algorithms with guaranteed error bounds for general graphs and some special graphs as well.
Journal: Journal of Discrete Algorithms - Volume 6, Issue 2, June 2008, Pages 341–351