| 講演名 | 2003/9/18 キャタピラネットワークにおけるパス彩色 高井 洋明, 金谷 隆志, 松林 昭, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | (有向)パス彩色問題は,与えられたグラフGとG上の(有向)パス集合Pに対し,互いに交わるパス同士が異なる色を持つように最小数の色を用いてPを彩色する問題であり, WDM光ネットワークにおいて通信要求に対して効率的に波長を割り当てる問題に応用がある.小文ではGが2分キャタピラに制限されていても有向パス彩色問題はNP困難であることを示す.さらに,与えられた2分キャタピラGとG上の有向パス集合Pに対して,高々8/5L色を用いてPを彩色する多項式時間アルゴリズムを与える.ただし,LはGの1辺を同じ向きに通過するパス数の最大値である. |
| 抄録(英) | 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. |
| キーワード(和) | キャタピラ / パス彩色 / NP困難 / 近似アルゴリズム |
| キーワード(英) | caterpillar / path coloring / NP-hardness / approximation algorithm |
| 資料番号 | COMP2003-39 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2003/9/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | キャタピラネットワークにおけるパス彩色 |
| サブタイトル（和） | |
| タイトル（英） | Path Coloring on Caterpillars |
| サブタイトル（和） | |
| キーワード(1)（和/英） | キャタピラ / caterpillar |
| キーワード(2)（和/英） | パス彩色 / path coloring |
| キーワード(3)（和/英） | NP困難 / NP-hardness |
| キーワード(4)（和/英） | 近似アルゴリズム / approximation algorithm |
| 第 1 著者 氏名（和/英） | 高井 洋明 / Hiroaki TAKAI |
| 第 1 著者 所属（和/英） | 金沢大学大学院自然科学研究科電子情報システム専攻 Graduate School of Natural Science and Technology, Kanazawa University |
| 第 2 著者 氏名（和/英） | 金谷 隆志 / Takashi KANATANI |
| 第 2 著者 所属（和/英） | 金沢大学大学院自然科学研究科電子情報システム専攻 Graduate School of Natural Science and Technology, Kanazawa University |
| 第 3 著者 氏名（和/英） | 松林 昭 / Akira MATSUBAYASHI |
| 第 3 著者 所属（和/英） | 金沢大学工学部情報システム工学科 Department of Information and Systems Engineering, Kanazawa University |
| 発表年月日 | 2003/9/18 |
| 資料番号 | COMP2003-39 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 326 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |