TY - JOUR
T1 - Complexity of minimal tree routing and coloring
AU - Chen, Xujin
AU - Hu, Xiaodong
AU - Jia, Xiaohua
PY - 2005
Y1 - 2005
N2 - Let G be a undirected connected graph. Given a set of g groups each being a subset of V(G), tree routing and coloring 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 how to find a tree routing and coloring that uses minimal number of colors, which finds an application of setting up multicast connections in optical networks. We first prove Ω(g1-ε)-inapproximability of the problem even when G is a mesh, and then we propose some approximation algorithms with provable performance guarantees for general graphs and some special graphs as well. © Springer-Verlag Berlin Heidelberg 2005.
AB - Let G be a undirected connected graph. Given a set of g groups each being a subset of V(G), tree routing and coloring 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 how to find a tree routing and coloring that uses minimal number of colors, which finds an application of setting up multicast connections in optical networks. We first prove Ω(g1-ε)-inapproximability of the problem even when G is a mesh, and then we propose some approximation algorithms with provable performance guarantees for general graphs and some special graphs as well. © Springer-Verlag Berlin Heidelberg 2005.
UR - http://www.scopus.com/inward/record.url?scp=25144464391&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-25144464391&origin=recordpage
M3 - 21_Publication in refereed journal
VL - 3521
SP - 6
EP - 15
JO - Lecture Notes in Computer Science
JF - Lecture Notes in Computer Science
SN - 0302-9743
T2 - First International Conference on Algorithmic Applications in Management, AAIM 2005
Y2 - 22 June 2005 through 25 June 2005
ER -