K-縮退グラフに含まれる誘導木の列挙

概要

論文の詳細を見る
本稿では,k- 縮退グラフに含まれる誘導木 (連結かつ非巡回な誘導部分グラフ) を,効率よく列挙するアルゴリズムを与える.グラフ G=(V,E) が k-縮退 (k-degenerate) であるとは,G の任意の部分グラフが高々 k の次数を持つ頂点を含むときをいう.これまで,制約のある誘導部分グラフの列挙に関しては,連結な誘導グラフ (Avis,Fukuda,DAM,1996) や,コードレスパス,コードレスサイクル (宇野,第 92 回アルゴリズム研究会,2003) の列挙に関する先行研究があるが,誘導木については知られていない.最大次数が d のとき,誘導木 1 つ当たり O(d) 遅延の列挙アルゴリズムは容易に構成できるが,これをどの程度まで改善できるかは未解決の問題である.我々のアルゴリズムは,入力グラフ G が k- 縮退グラフであるとき,誘導木を 1 つ当たりならし O(k) 時間で列挙する.系として,k が定数ならば,誘導木を 1 つたり,ならし定数時間で列挙可能である.
2014-06-06