
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Path Coloring on Binary Caterpillars
Hiroaki TAKAI Takashi KANATANI Akira MATSUBAYASHI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E89D
No.6
pp.19061913 Publication Date: 2006/06/01 Online ISSN: 17451361
DOI: 10.1093/ietisy/e89d.6.1906 Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithm Theory Keyword: path coloring, wavelength routing, caterpillar,
Full Text: PDF>>
Summary:
The path coloring problem is to assign the minimum number of colors to a given set P of directed paths on a given symmetric digraph D so that no two paths sharing an arc have the same color. The problem has applications to efficient assignment of wavelengths to communications on WDM optical networks. In this paper, we show that the path coloring problem is NPhard even if the underlying graph of D is restricted to a binary caterpillar. Moreover, we give a polynomial time algorithm which constructs, given a binary caterpillar G and a set P of directed paths on the symmetric digraph associated with G, a path coloring of P with at most colors, where L is the maximum number of paths sharing an edge. Furthermore, we show that no local greedy path coloring algorithm on caterpillars in general uses less than colors.

