| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-01-30 09:30 グラフ点彩色問題の分散分枝限定解法ParaBSCに対するVNSに基づく性能強化 ○道後幸寛・田岡智志・渡邉敏正（広島大）  CST2008-52 |
|
| 抄録 | （和） | グラフの点彩色とは，与えられた無向グラフ$G$において隣接する(辺で結ば れている) 頂点対が異なる色となるようにすべての頂点に色を塗ることである． 点彩色問題は$G$を点彩色するのに必要な最小色数及び そのときの点彩色を求めることであるが，一 般にNP困難である．そこで高速に最適解を得るために分散分枝限定解法 ParaBSC が提案されているが，それでも頂点数が少し大きくなるだけで非常に 長い計算時間を要する．本研究は，発見的彩色法VNS\_TOの利用によるParaBSCの高 速化を図り，計算機実験に基づく性能評価を示す． |
| （英） | Given an undirected graph $G$, a coloring is an assignment of colors to vertices of $G$ such that any pair of adjacent vertices (they are linked by an edge) have different colors. The graph coloring problem is a problem of obtaining the smallest number of colors needed to color all vertices of $G$ as well as its coloring (called ``an exact coloring''), and it is known to be NP-hard. So a distributed branch-and-bound algorithm ParaBSC has been proposed in order to obtain an exact coloring rapidly. Even if it is used, its computing time is likely to increase exponentially. In this paper, ParaBSC is going to be enhanced by utilizing a heuristic coloring procedure VNS\_TO, and its capability is evaluated through computing experiment. |
|
| キーワード | （和） | グラフ点彩色問題 / 最小彩色数 / 近傍探索 / 発見的解法 / 分枝限定法 / / / |
| （英） | Graph coloring problems / chromatic numbers / variable neighborhood search / approximation algorithms / branch-and-bound algorithms / / / | |
| 文献情報 | 信学技報, vol. 108, 2009年1月. | |
| 資料番号 | ||
| 発行日 | 2009-01-22 (CST) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CST2008-52 |
|
| 研究会情報 | |
| 研究会 | MSS |
| 開催期間 | 2009-01-29 - 2009-01-30 |
| 開催地（和） | 神奈川県産業振興センター会議室(第一会議室) |
| 開催地（英） | Kanagawa Industrial Promotion Center |
| テーマ（和） | コンカレント工学一般 |
| テーマ（英） | Concurrent Systems |
| 講演論文情報の詳細 | |
| 申込み研究会 | MSS |
| 会議コード | 2009-01-CST |
| 本文の言語 | 日本語 |
| タイトル（和） | グラフ点彩色問題の分散分枝限定解法ParaBSCに対するVNSに基づく性能強化 |
| サブタイトル（和） | |
| タイトル（英） | VNS-based Enhancing of a Distributed Branch-and-Bound Algorithm ParaBSC for the Graph Coloring Problem |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフ点彩色問題 / Graph coloring problems |
| キーワード(2)（和/英） | 最小彩色数 / chromatic numbers |
| キーワード(3)（和/英） | 近傍探索 / variable neighborhood search |
| キーワード(4)（和/英） | 発見的解法 / approximation algorithms |
| キーワード(5)（和/英） | 分枝限定法 / branch-and-bound algorithms |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 道後 幸寛 / Yukihiro Dougo / ドウゴ ユキヒロ |
| 第1著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 田岡 智志 / Satoshi Taoka / タオカ サトシ |
| 第2著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 渡邉 敏正 / Toshimasa Watanabe / ワタナベ トシマサ |
| 第3著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2009-01-30 09:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | MSS |
| 資料番号 | CST2008-52 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | no.415 |
| ページ範囲 | pp.61-66 |
| ページ数 | 6 |
| 発行日 | 2009-01-22 (CST) |
[研究会発表申込システムのトップページに戻る]