Inapproximability and approximability of minimal tree routing and coloring

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)22_Publication in policy or professional journal

View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)341-351
Journal / PublicationJournal of Discrete Algorithms
Issue number2
Publication statusPublished - Jun 2008


Let G be an undirected connected graph. Given a set of g groups each being a subset of 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 - ε)-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. © 2007 Elsevier B.V. All rights reserved.

Research Area(s)

  • Approximability, Tree coloring, Tree routing, Vertex coloring

Citation Format(s)