6533b874fe1ef96bd12d60a6

RESEARCH PRODUCT

Paths Coloring Algorithms in Mesh Networks

Olivier TogniMustapha Kchikech

subject

AlgorithmicsMesh networkingPath (graph theory)Approximation algorithmPolygon meshFractional coloringTelecommunications networkAlgorithmTime complexityMathematics

description

In this paper, we will consider the problem of coloring directed paths on a mesh network. A natural application of this graph problem is WDM-routing in all-optical networks. Our main result is a simple 4-approximation algorithm for coloring line-column paths on a mesh. We also present sharper results when there is a restriction on the path lengths. Moreover, we show that these results can be extended to toroidal meshes and to line-column or column-line paths.

yearjournalcountryeditionlanguage
2003-01-01
https://doi.org/10.1007/3-540-45066-1_15