| 講演名 | 2011-12-16 グラフの帯域幅連続多重彩色を求めるアルゴリズム 西川 和秀, 西関 隆夫, 周 暁, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 単純グラフGの各点vには正整数重みb(v)が,各辺(v,w)には非負整数重みb(v,w)が付いているとき,Gの帯域幅連続多重彩色とは,Gの各点vに連続したb(v)個の正整数(色)を割り当てることである.ただし,各辺(v,w)について,点vに割り当てられた色と点wに割り当てられた色はb(v,w)+1以上離れていなければならない.点に割り当てられた最大の整数はその彩色のスパンと呼ばれる.本文では,まずこのような彩色の基本的な性質を調べる.次に,直並列グラフGの帯域幅連続多重彩色でスパンが最小なものを求める問題に対して,擬多項式時間厳密アルゴリズムおよび完全多項式時間近似スキームを与える.最後に,これらの結果を部分k-木,即ち,木幅が定数であるグラフに拡張する. |
| 抄録(英) | Let G be a simple graph in which each vertex v has a positive integer weight b(v) and each edge (v, w) has a nonnegative integer weight b(v, w). A bandwidth consecutive multicoloring of G assigns each vertex v a specified number b(v) of consecutive positive integers so that, for each edge (v, w), all integers assigned to vertex v differ from all integers assigned to vertex w by more than b(v, w). The maximum integer assigned to a vertex is called the span of the coloring. In the paper, we first investigate fundamental properties of such a coloring. We then obtain a pseudo polynomial-time exact algorithm and a fully polynomial-time approximation scheme for the problem of finding such a coloring of a given graph with the minimum span for the case G is a series-parallel graph. We finally extend the results to the case G is a partial k-tree, that is, G has a bounded tree-width. |
| キーワード(和) | 帯域幅彩色 / 周波数割り当て / 多重彩色 / 直並列グラフ / 部分k-木 / アルゴリズム / 無閉路的グラフ / 近似 / FPTAS |
| キーワード(英) | Bandwidth coloring / Channel assignment / Multicoloring / Series-parallel graph / Partial k-tree / Algorithm / Acyclic orientation / Approximation / FPTAS |
| 資料番号 | COMP2011-38 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2011/12/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | グラフの帯域幅連続多重彩色を求めるアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Algorithms for Bandwidth Consecutive Multicolorings of Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 帯域幅彩色 / Bandwidth coloring |
| キーワード(2)（和/英） | 周波数割り当て / Channel assignment |
| キーワード(3)（和/英） | 多重彩色 / Multicoloring |
| キーワード(4)（和/英） | 直並列グラフ / Series-parallel graph |
| キーワード(5)（和/英） | 部分k-木 / Partial k-tree |
| キーワード(6)（和/英） | アルゴリズム / Algorithm |
| キーワード(7)（和/英） | 無閉路的グラフ / Acyclic orientation |
| キーワード(8)（和/英） | 近似 / Approximation |
| キーワード(9)（和/英） | FPTAS / FPTAS |
| 第 1 著者 氏名（和/英） | 西川 和秀 / Kazuhide NISIKAWA |
| 第 1 著者 所属（和/英） | 関西学院大学理工学部 School of Science and Engineering, Kwansei Gakuin University |
| 第 2 著者 氏名（和/英） | 西関 隆夫 / Takao NISHIZEKI |
| 第 2 著者 所属（和/英） | 関西学院大学理工学部 School of Science and Engineering, Kwansei Gakuin University |
| 第 3 著者 氏名（和/英） | 周 暁 / Xiao ZHOU |
| 第 3 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 発表年月日 | 2011-12-16 |
| 資料番号 | COMP2011-38 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | 360 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |