algorithm - 制約された次数+制限された直径の最小スパニングツリーのアルゴリズム？

Question

スパニングツリーの計算に3種類の制限があるとします。

1. 制約の程度（例：スパニングツリー内のノードは、他の3つのノードまでしか接続できません）
2. 境界の直径（例：すべてのエッジの重みを合計すると、100を超えることはできません）。
   2.1。可能であれば、この基準を満たすすべてのサブツリーを表示します。
3. 両方

これを解決するために、私を狂わせない優れたアルゴリズムはありますか？これをかなり大きな入力（1000以上のノード）で実行する必要があるので、複雑さも高くなりすぎないようにします。

Answer 1

次数制約スパニング ツリー問題は NP 完全です。http://en.wikipedia.org/wiki/Degree-constrained_spanning_treeを参照してください。したがって、適切な (つまり、多項式の) アルゴリズムはありません。ただし、近似アルゴリズムはあります。

Google 検索では、有界直径スパニング ツリーの問題も同様に難しいことが示されているようです。