お知らせ 2023年度・2024年度 学生員 会費割引キャンペーン実施中です
お知らせ 技術研究報告と和文論文誌Cの同時投稿施策(掲載料1割引き)について
お知らせ 電子情報通信学会における研究会開催について
お知らせ NEW 参加費の返金について
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2008-05-13 13:55
3 < n/k < 4に対する平面グラフのn/k-彩色問題のNP完全性
庄司將一上嶋章宏阪電通大COMP2008-11
抄録 (和) 本稿では,$H$-彩色問題($H$は単純無向グラフ)の部分問題である$n/k$-彩色問題($n$, $k$は$n/k \ge 2$である自然数)について考える.一般のグラフに対する$n/k$-彩色問題の計算複雑さは,$H$-彩色問題に関する既存結果から明らかである.一方,平面グラフに対する$n/k$-彩色問題の計算複雑さは未解決である.本問題は,$2 < n/k < 3$および$3 < n/k < 4$である任意の$n/k$に対し計算複雑さを解析することで充分であり,$2 < n/k < 3$である$n/k$でのNP完全性はすでに証明した.本稿では,$3 < n/k < 4$である任意の$n/k$に対するNP完全性を示す. 
(英) This report considers the $n/k$-coloring problem, which is a subproblem for the $H$-coloring problem, where $H$ is a simple undirected graph and $n$, $k$ are positive integers with $n/k \ge 2$. The computational complexities of $n/k$-coloring problems on general graphs can be obtained directly from the prevoius results concerning $H$-coloring problems. However, the complexities of the problems on \textit{planar graphs} are still open. The analysis for any fixed $n/k$ with $2 < n/k < 3$ or $3 < n/k < 4$ is sufficient to prove that the problems on planar graphs are NP-complete, and NP-completeness of the problems with $2 < n/k < 3$ has been shown in our previous works. This report proves that the problems with $3 < n/k < 4$ are NP-complete.
キーワード (和) $H$-彩色 / $n/k$-彩色 / NP完全 / 平面グラフ / / / /  
(英) $H$-coloring / $n/k$-coloring / NP-complete / planar graph / / / /  
文献情報 信学技報, vol. 108, no. 29, COMP2008-11, pp. 25-32, 2008年5月.
資料番号 COMP2008-11 
発行日 2008-05-06 (COMP) 
ISSN Print edition: ISSN 0913-5685    Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2008-11

研究会情報
研究会 COMP  
開催期間 2008-05-13 - 2008-05-13 
開催地(和) 九州産業大学 
開催地(英) Kyushu Sangyo University 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2008-05-COMP 
本文の言語 日本語 
タイトル(和) 3 < n/k < 4に対する平面グラフのn/k-彩色問題のNP完全性 
サブタイトル(和)  
タイトル(英) NP-Completeness of Planar n/k-Coloring Problems for n/k Between 3 and 4 
サブタイトル(英)  
キーワード(1)(和/英) $H$-彩色 / $H$-coloring  
キーワード(2)(和/英) $n/k$-彩色 / $n/k$-coloring  
キーワード(3)(和/英) NP完全 / NP-complete  
キーワード(4)(和/英) 平面グラフ / planar graph  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 庄司 將一 / Masakazu Shoji / ショウジ マサカズ
第1著者 所属(和/英) 大阪電気通信大学 (略称: 阪電通大)
Osaka Electro-Communication University (略称: Osaka Electro-Communication Univ.)
第2著者 氏名(和/英/ヨミ) 上嶋 章宏 / Akihiro Uejima / ウエジマ アキヒロ
第2著者 所属(和/英) 大阪電気通信大学 (略称: 阪電通大)
Osaka Electro-Communication University (略称: Osaka Electro-Communication Univ.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第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著者 所属(和/英) (略称: )
(略称: )
講演者 第1著者 
発表日時 2008-05-13 13:55:00 
発表時間 35分 
申込先研究会 COMP 
資料番号 COMP2008-11 
巻番号(vol) vol.108 
号番号(no) no.29 
ページ範囲 pp.25-32 
ページ数
発行日 2008-05-06 (COMP) 


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

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


IEICE / 電子情報通信学会