電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2012-03-09 14:45
グラフ点彩色問題の発見的解法の性能比較
小新雄太田岡智志渡邉敏正広島大
技報オンラインサービス実施中
抄録 (和) グラフ点彩色とは,与えられた無向グラフ$G=(V,E)$において隣接する頂点対が異なる色となるようにすべての頂点に色を塗ることである.グラフ点彩色問題はGを点彩色するのに必要な最小色数及びそのときの点彩色を求めることである.この問題はNP困難であることが知られており,最適解を得るための厳密解法の実行には非常に長い時間を要する.そこで最適解が得られるとは限らないが,比較的短時間で終了する発見的解法が提案されている.本研究では,グラフ点彩色問題の代表的な発見的解法に焦点を当て計算機実験に基づきこれらの性能を比較する. 
(英) Graph coloring is an assignment of colors to vertices of a given undirected graph G=(V,E) such that any pair of adjacent vertices receive different colors. The graph coloring problem is a problem of obtaining coloring with the smallest number of colors. The problem is known to be NP-hard, and finding an optimum solution needs long computing time, requiring heuristic algorithms that give us good solutions, in reasonable computing time. In this paper, we compare performance of well-known heuristic algorithms based on computing experiment.
キーワード (和) グラフ点彩色問題 / NP困難 / 発見的解法 / 性能比較 / / / /  
(英) Graph coloring problem / NP-hardness / Heuristics / Performance comparison / / / /  
文献情報 信学技報, vol. 111, no. 465, CAS2011-145, pp. 213-218, 2012年3月.
資料番号 CAS2011-145 
発行日 2012-03-01 (CAS, SIP, CS) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 CAS CS SIP  
開催期間 2012-03-08 - 2012-03-09 
開催地(和) 新潟大学駅南キャンパス「ときめいと」 
開催地(英) The University of Niigata 
テーマ(和) ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般 
テーマ(英) Network Processor, Signal Processing for communication, and Wireless LAN/PAN, etc. 
講演論文情報の詳細
申込み研究会 CAS 
会議コード 2012-03-CAS-CS-SIP 
本文の言語 日本語 
タイトル(和) グラフ点彩色問題の発見的解法の性能比較 
サブタイトル(和)  
タイトル(英) Performance Comparison of Heuristic Algorithms for the Graph Coloring Problem 
サブタイトル(英)  
キーワード(1)(和/英) グラフ点彩色問題 / Graph coloring problem  
キーワード(2)(和/英) NP困難 / NP-hardness  
キーワード(3)(和/英) 発見的解法 / Heuristics  
キーワード(4)(和/英) 性能比較 / Performance comparison  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 小新 雄太 / Yuta Koshin / コシン ユウタ
第1著者 所属(和/英) 広島大学 大学院工学研究院 (略称: 広島大)
Graduate School of Engineering,Hiroshima University (略称: Hiroshima Univ.)
第2著者 氏名(和/英/ヨミ) 田岡 智志 / Satoshi Taoka / タオカ サトシ
第2著者 所属(和/英) 広島大学 大学院工学研究院 (略称: 広島大)
Graduate School of Engineering,Hiroshima University (略称: Hiroshima Univ.)
第3著者 氏名(和/英/ヨミ) 渡邉 敏正 / Toshimasa Watanabe / ワタナベ トシマサ
第3著者 所属(和/英) 広島大学 大学院工学研究院 (略称: 広島大)
Graduate School of Engineering,Hiroshima University (略称: Hiroshima Univ.)
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2012-03-09 14:45:00 
発表時間 25 
申込先研究会 CAS 
資料番号 IEICE-CAS2011-145,IEICE-SIP2011-165,IEICE-CS2011-137 
巻番号(vol) IEICE-111 
号番号(no) no.465(CAS), no.466(SIP), no.467(CS) 
ページ範囲 pp.213-218 
ページ数 IEICE-6 
発行日 IEICE-CAS-2012-03-01,IEICE-SIP-2012-03-01,IEICE-CS-2012-03-01 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会