小熊, 卓, 中野, 眞一, 西関, 隆夫
全国大会講演論文集
第45回
(基礎理論及び基礎技術),
59-60,
1992-09-28
...(a)グラフG_Tの,任意の4点以上からなる点誘導部分グラフは閉路でない(b)cはグラフG_Tの点彩色である.本文では,cがグラフGの3色による点彩色である時のc-三角化を考える.Gが3色で点彩色されている時,Gをc-三角化するO(α(n)・n)時間アルゴリズムが知られている.ここでα(n)はアッカーマン関数の逆関数である.本文ではO(n)時間アルゴリズムを与える.グラフのc-三角化は以下のような系統木推定問題...
情報処理学会
