最小次数全域木

グラフ理論において、最小次数全域木とは、連結グラフの辺の部分集合であり、すべての頂点をサイクルなしで接続し、かつその頂点の最大次数が可能な限り小さいもののことである。つまり、最大次数が最小である全域木のことである。

決定問題とは、グラフGと整数kが与えられたとき、Gには次数がkを超える頂点が存在しない全域木が存在するかどうかを問う問題である。これは次数制約付き全域木問題とも呼ばれる。

無向グラフの最小次数全域木を見つけることはNP困難である。これはハミルトン経路問題からの還元を構築することで示すことができる。有向グラフの場合も、最小次数全域木を見つけることはNP困難である。^{[ 1 ]}

R. KrishmanとB. Raghavachari（2001）は、有向グラフの問題を解くための準多項式時間近似アルゴリズムを提案している。 ^{[ 1 ]}

M. Haque、Md. R. Uddin、およびMd. A. Kashem（2007）は、次数が小さい直並列グラフの最小次数全域木を見つけることができる線形時間アルゴリズムを発見した。^{[ 2 ]}

G. Yao、D. Zhu、H. Li、およびS. Ma（2008）は、有向非巡回グラフの最小次数全域木を見つけることができる多項式時間アルゴリズムを発見した。^{[ 3 ]}