n/k-彩色での階層構造間に存在する平面グラフの構成手法

スポンサーリンク

概要

• 論文の詳細を見る

• 古典的なn-彩色では,色数nの増加に伴い彩色可能なグラフは真に増加し,n-彩色に関する自明な階層構造が存在する.n-彩色の一般化であるn/k-彩色はその階層構造を真に細分する性質を持ち,n'/k'<n/kに対しn'/k'-彩色可能なグラフは全てn/k-彩色可能であるが,その逆は成立しない.一方,2<n/k<3に対し,平面グラフのn/k-彩色問題がNP完全性であることが示されており,計算量の観点では当該範囲のn/kに対し違いがない.そこで本研究では,2<n'/k'<3に関する階層構造に注目し,階層構造間に存在する平面グラフの構成を示すことで,2<n'/k'<n/k<3に対し,平面グラフに対象を限定してもn'/k'-彩色とn/k-彩色に明確な能力差があることを示す.

• 2008-01-24

著者

• 上嶋 章宏

  大阪電気通信大学工学研究科情報工学専攻

• 庄司 將一

  大阪電気通信大学大学院工学研究科情報工学専攻

• 上嶋 章宏

  大阪電気通信大学大学院

• 井口 雄弥

  大阪電気通信大学総合情報学部情報工学科

• 庄司 將一

  大阪電気通信大学工学研究科

関連論文

• 盤面および使用セルを考慮した回転型セル迷路の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-エンターテイメントの数理」)

もっと見る 閉じる

スポンサーリンク