0

固定数のノードとエッジを持つグラフがあるとします。ただし、すべてのノードが常にアクティブであるとは限らないため、グラフが切断されます。この種の状況では、アクティブなままの場合にグラフを常に接続したままにする頂点の最小セットを見つけたいと思います。

どうすればこの問題を解決できますか? この問題は既知の問題にマッピングできますか?

4

2 に答える 2

0

これは、Connected Dominating Set のように聞こえます。

于 2013-11-21T13:36:49.183 に答える