@techreport{oai:ipsj.ixsq.nii.ac.jp:00101704,
 author = {和佐, 州洋 and 有村, 博紀 and 宇野, 毅明 and Kunihiro, Wasa and Hiroki, Arimura and Takeaki, Uno},
 issue = {17},
 month = {Jun},
 note = {本稿では，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 つたり，ならし定数時間で列挙可能である．},
 title = {K-縮退グラフに含まれる誘導木の列挙},
 year = {2014}
}