All-to-all routing and coloring in weighted trees of rings

Abstract

A tree of rings is an undirected graph obtained from the union of rings, which intersect two by two in at most one node, such that any two nodes are connected by exactly two edge-disjoint paths. In this paper, we consider symmetric directed trees of rings with weighted nodes. A routing for a weighted digraph is a collection of directed paths (dipaths), such that for each ordered pair of nodes (x 1 ; x 2 ) with respective weights w 1 and w 2 , there are w 1 w 2 dipaths (possibly not distinct) from x 1 to x 2 . Motivated by the Wavelength Division Multiplexing (WDM) technology in all-optical networks, we study the problem of nding a routing which can be colored by the fewest number of colors so that dipaths of the same color are arc-disjoint. We prove that this minimum number of colors (wavelengths) is equal to the maximum number of dipaths that share one arc (load), minimized over all routings. The problem can be efficiently solved (dipaths found and colored) using cut properties.