Complexity of minimal tree routing and coloring
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 6-15 |
Journal / Publication | Lecture Notes in Computer Science |
Volume | 3521 |
Publication status | Published - 2005 |
Conference
Title | First International Conference on Algorithmic Applications in Management, AAIM 2005 |
---|---|
Place | China |
City | Xian |
Period | 22 - 25 June 2005 |
Link(s)
Abstract
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.
Citation Format(s)
Complexity of minimal tree routing and coloring. / Chen, Xujin; Hu, Xiaodong; Jia, Xiaohua.
In: Lecture Notes in Computer Science, Vol. 3521, 2005, p. 6-15.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review