IEICE TRANSACTIONS on Information
Path Coloring on Binary Caterpillars
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 NP-hard 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
- Publication
- IEICE TRANSACTIONS on Information Vol.E89-D No.6 pp.1906-1913
- Publication Date
- 2006/06/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e89-d.6.1906
- Type of Manuscript
- PAPER
- Category
- Algorithm Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroaki TAKAI, Takashi KANATANI, Akira MATSUBAYASHI, "Path Coloring on Binary Caterpillars" in IEICE TRANSACTIONS on Information,
vol. E89-D, no. 6, pp. 1906-1913, June 2006, doi: 10.1093/ietisy/e89-d.6.1906.
Abstract: 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 NP-hard 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
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.6.1906/_p
Copy
@ARTICLE{e89-d_6_1906,
author={Hiroaki TAKAI, Takashi KANATANI, Akira MATSUBAYASHI, },
journal={IEICE TRANSACTIONS on Information},
title={Path Coloring on Binary Caterpillars},
year={2006},
volume={E89-D},
number={6},
pages={1906-1913},
abstract={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 NP-hard 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
keywords={},
doi={10.1093/ietisy/e89-d.6.1906},
ISSN={1745-1361},
month={June},}
Copy
TY - JOUR
TI - Path Coloring on Binary Caterpillars
T2 - IEICE TRANSACTIONS on Information
SP - 1906
EP - 1913
AU - Hiroaki TAKAI
AU - Takashi KANATANI
AU - Akira MATSUBAYASHI
PY - 2006
DO - 10.1093/ietisy/e89-d.6.1906
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2006
AB - 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 NP-hard 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
ER -
English
