Enumeration of subtrees of trees

Weigen Yan and Yeong-Nan Yeh
Theoretical Computer Science
Volume 369, Issues 1-3, 15 December 2006, Pages 256-268
http://dx.doi.org/10.1016/j.tcs.2006.09.002

与えられた木にいくつ部分木があるか，という問題．
SzekelyとWang (2005) は頂点数nを固定したとき，パスが部分木の数を最小化し，スターが部分木の数を最大化することを証明した．
この論文では，直径がd以上で頂点数nの木の中で最も多くの部分木を持つ木，および，最大次数がΔ以上で頂点数nの木の中で最も少ない部分木を持つ木を特徴付けている．
そのために，与えられた木の部分木の数をenumerateする母関数を計算する線形時間アルゴリズムを与えている．
(本当は，それよりも一般的な問題を線形時間で解いている．)