平面グラフのn/k-彩色問題の計算複雑さ
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,H-彩色問題の部分問題であるn/k-彩色問題(Circular Coloring)について考える(但し,Hは単純無向グラフであり,n,kはn/k≧2である自然数である).グラフHが2部グラフのときに限り,H-彩色問題が多項式時間可解であり,それ以外ではNP完全であることが知られており,その部分問題であるn/k-彩色問題でも同様の結果となる.一方,平面グラフに対するn/k-彩色(あるいはH-彩色)問題の計算複雑さは部分的にしか解決しておらず,未解決のままである.平面グラフに限定した場合,2<n/k<4である全てのn/kについてn/k-彩色問題の計算複雑さを明らかにすることで十分であるが,本稿では2<n/k<3に対しn/k-彩色問題がNP完全であることを示す.
- 社団法人電子情報通信学会の論文
- 2007-06-22
著者
関連論文
- 盤面および使用セルを考慮した回転型セル迷路のPSPACE完全性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- n/k-彩色での階層構造間に存在する平面グラフの構成手法
- 3
- Anti-Webによる$H$-彩色に関する新たな階層構造の導出 (理論計算機科学の深化と応用)
- 六角格子,三角格子上でのスリザーリンクのASP完全性について
- 5M-9 ZKIPを実現するために組合せ問題を基本機能に分解する枠組み(アルゴリズム,学生セッション,ソフトウェア科学・工学)
- 平面グラフのn/k-彩色問題の計算複雑さ
- 2
- 8面,20面ダイスを用いたRolling Dice PuzzleのNP完全性(アルゴリズムとデータ構造・計算複雑度)
- 回転型セル迷路のPSPACE完全性(アルゴリズムとデータ構造・計算複雑度)
- 2-K-6 色数とおじゃまぷよを制限した一般化ぷよぷよの連鎖数判定問題のNP完全性(ワークショップ「娯楽のOR-エンターテイメントの数理」)