Coloring all directed paths in a symmetric tree, with an application to optical networks
✍ Scribed by Luisa Gargano; Pavol Hell; Stephane Perennes
- Publisher
- John Wiley and Sons
- Year
- 2001
- Tongue
- English
- Weight
- 169 KB
- Volume
- 38
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
Let T be a symmetric directed tree, i.e., an undirected tree with each edge viewed as two opposite arcs. We prove that the minimum number of colors needed to color the set of all directed paths in T, so that two paths of the same color never use the same directed arc of T, is equal to the maximum number of different paths that contain the same arc of T. The proof implies a polynomial time algorithm for actually coloring the paths with the minimum number of colors. When only a subset of the directed paths is to be colored, the problem is known to be NP‐complete; we describe certain instances of the problem which can be efficiently solved. These results are applied to WDM (wavelength‐division multiplexing) routing in all‐optical networks. In particular, we solve the all‐to‐all gossiping problem in optical networks. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 183–196, 2001