Complexity of Minimal Tree Routing and Coloring

Xujin Chen, Xiao-Dong Hu, Xiaohua Jia

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 Ω(g 1 − ε)-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.
BibTeX
@inproceedings{chen2005complexity,
  author = {Xujin Chen and Xiao-Dong Hu and Xiaohua Jia},
  title = {{Complexity of Minimal Tree Routing and Coloring}},
  booktitle = {AAIM},
  year = {2005},
  doi = {10.1007/11496199\_3},
}

Loading related content...

Figure