Complexity of minimal tree routing and coloring

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)6-15
Journal / PublicationLecture Notes in Computer Science
Volume3521
Publication statusPublished - 2005

Conference

TitleFirst International Conference on Algorithmic Applications in Management, AAIM 2005
PlaceChina
CityXian
Period22 - 25 June 2005

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 journalpeer-review