| Presentation | 2003/9/18 Path Coloring on Caterpillars Hiroaki TAKAI, Takashi KANATANI, Akira MATSUBAYASHI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | For a given graph G and a set P of (directed) paths on G, the (directed) path coloring problem is to assign colors the paths of P so that no two intersecting paths have the same color and that the total number of the used colors is minimized. The path coloring problem has applications to the wavelength assignment problems on WDM optical networks. In this report, we show that the directed path coloring problem is NP-hard even if G is restricted to a binary caterpillar. Moreover we give a polynomial time algorithm constructing, given a binary caterpillar G and a set P of directed paths on G, a directed path coloring of P by using at most 8/5L colors, where L is the maximum number of paths of P which pass an edge of G in the same direction. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | caterpillar / path coloring / NP-hardness / approximation algorithm |
| Paper # | COMP2003-39 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2003/9/18(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Path Coloring on Caterpillars |
| Sub Title (in English) | |
| Keyword(1) | caterpillar |
| Keyword(2) | path coloring |
| Keyword(3) | NP-hardness |
| Keyword(4) | approximation algorithm |
| 1st Author's Name | Hiroaki TAKAI |
| 1st Author's Affiliation | Graduate School of Natural Science and Technology, Kanazawa University() |
| 2nd Author's Name | Takashi KANATANI |
| 2nd Author's Affiliation | Graduate School of Natural Science and Technology, Kanazawa University |
| 3rd Author's Name | Akira MATSUBAYASHI |
| 3rd Author's Affiliation | Department of Information and Systems Engineering, Kanazawa University |
| Date | 2003/9/18 |
| Paper # | COMP2003-39 |
| Volume (vol) | vol.103 |
| Number (no) | 326 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |