最大次数ΔのC_4フリーグラフの(2Δ-4)彩色数を数え上げるためのマルコフ連鎖モンテカルロ法
スポンサーリンク
概要
- 論文の詳細を見る
本稿では、C_4フリーグラフのk-彩色数を数え上げるための高速なマルコフ連鎖モンテカルロ法(MCMC)を提案する。グラフの最大次数をΔとすると、Δ≥6のときはk≥2Δ-4に対して、またΔ=3,4,5のときはそれぞれk≥5,6,7に対して、k-彩色数の数え上げが多項式時間で可能である。実行時間は0(Δ^2nlogn)である。本結果は、特にmax(2Δ-4,Δ+2)≤k<11/6Δ、3≤Δ≤23のときに、C_4フリーグラフに対する初めての多項式時間k-彩色数数え上げアルゴリズムである。
- 一般社団法人情報処理学会の論文
- 2004-07-27
著者
関連論文
- 球面幾何学に基づく新たなジャグリング
- Spherical Juggling におけるパターン表記法
- DNA計算によるAES暗号の解読
- Ninf-G上の分散並列計算システムの開発
- ハノイの塔問題に対する再帰方程式の一般化とその厳密解析
- 二値アルファベット上の有限オートマトンの等価変換と状態数解析
- 一般化はさみ将棋のEXPTIME完全性
- 文理複合型情報系組織におけるプログラミング教育の実践例(プログラミング,何をどう教えているか)
- 最大次数ΔのC_4フリーグラフの(2Δ-4)彩色数を数え上げるためのマルコフ連鎖モンテカルロ法
- Computing Phylogenetic Roots with Bounded Degrees and Errors is Hard (Evolutionary Advancement in Fundamental Theories of Computer Science)
- A-026 インターネット上の遊休PCを利用した量子探索シミュレータの開発(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- RA-004 振幅を制限した無誤り量子計算について(A分野:モデル・アルゴリズム・プログラミング,査読付き論文)
- 正六角盤面上のポリオミノアチーブメントにおける先手必勝法