実践的な列挙アルゴリズムの理論構築

今年度の研究は、あいまいさを許容した対象を列挙する効率よい手法についての研究を行った。まず、クリークの列挙問題を拡張し、クリークに近い部分グラフを列挙する問題を定式化した。この定式化は以前の物に比べ、冗長な物を含まないという意味で利点があるが計算の上では基礎的なアルゴリズムが使えなくなり不利である。今年度はこの問題に対して、基礎的な方法を単純に用いた場合の困難生を証明し、また別の方法を用いると多項式時間列挙が可能なことを示した。また、実用面での改良を示し、疎なグラフでは短時間で計算が終了することを証明し、実際に実験でもアルゴリズムの実用性を示した。また、この結果をデータマイニングの頻出集合列挙問題に応用し、頻出集合に近いものを列挙する問題を定式化し、多項式時間アルゴリズムを提案した。このほか、データマイニング分野では、極大な頻出シークエンスパターンの多項式時間列挙アルゴリズム、頻出幾何グラフの多項式時間列挙アルゴリズムを開発した。両者共に今まで考えられてこなかったクラスであり、かつその問題に対して飽和パターンの導入に成功し、またその多項式時間列挙アルゴリズムの開発に成功している、グラフアルゴリズムの分野では、連結極大平面グラフの定数時間列挙アルゴリズム、整数分割の定数時間列挙アルゴリズムを新たに開発した。いずれも逆探索を用いた簡潔な列挙手法となっているところが特徴である。また、列挙の手法を応用し、順序木の一様ランダム生成を行う効率良いアルゴリズムの開発にも成功した。

今年度の研究は、あいまいさを許容した対象を列挙する効率よい手法についての研究を行った。まず、クリークの列挙問題を拡張し、クリークに近い部分グラフを列挙する問題を定式化した。この定式化は以前の物に比べ、冗長な物を含まないという意味で利点があるが計算の上では基礎的なアルゴリズムが使えなくなり不利である。今年度はこの問題に対して、基礎的な方法を単純に用いた場合の困難生を証明し、また別の方法を用いると多項式時間列挙が可能なことを示した。また、実用面での改良を示し、疎なグラフでは短時間で計算が終了することを証明し、実際に実験でもアルゴリズムの実用性を示した。また、この結果をデータマイニングの頻出集合列挙問題に応用し、頻出集合に近いものを列挙する問題を定式化し、多項式時間アルゴリズムを提案した。このほか、データマイニング分野では、極大な頻出シークエンスパターンの多項式時間列挙アルゴリズム、頻出幾何グラフの多項式時間列挙アルゴリズムを開発した。両者共に今まで考えられてこなかったクラスであり、かつその問題に対して飽和パターンの導入に成功し、またその多項式時間列挙アルゴリズムの開発に成功している、グラフアルゴリズムの分野では、連結極大平面グラフの定数時間列挙アルゴリズム、整数分割の定数時間列挙アルゴリズムを新たに開発した。いずれも逆探索を用いた簡潔な列挙手法となっているところが特徴である。また、列挙の手法を応用し、順序木の一様ランダム生成を行う効率良いアルゴリズムの開発にも成功した。