具有最小边权重和节点权重 >= Val 的子图
Subgraph with minimum edge weight and node weight >= Val
我遇到了这个问题 - 在无向图中，每个节点和边都有一个权重。所有的权重都是非负的。给定一个值S，找到边权值和最小的连通子图，使得其节点权值之和至少为S。
最明显的解决方案是考虑所有可能子图的蛮力方法。但是时间复杂度是指数级的。有没有更好的算法？我的直觉是我们可以将节点权重转换为边权重，然后应用生成树算法。但是我无法清楚地解决它。如何解决这个问题？
编辑：看来我对子图的描述不够清楚。所选子图必须是单个连通分量。我希望现在清楚了。
我认为这个问题是 NP 难的，通过对斯坦纳树问题的归约。给定一个图 G 和一组需要跨越的节点 S，将 S 中所有节点的权重设置为 1，将所有其他节点设置为 0。节点权重至少为 |S| 的子图具有最小总边成本的树必须是一棵树（如果有任何循环，从循环中删除一条边只会降低成本）并且必须连接所有需要跨越的节点。因此它是一棵斯坦纳树。总的来说，这个减少可以在多项式时间内计算，所以你的问题是 NP-hard。
我遇到了这个问题 - 在无向图中，每个节点和边都有一个权重。所有的权重都是非负的。给定一个值S，找到边权值和最小的连通子图，使得其节点权值之和至少为S。
最明显的解决方案是考虑所有可能子图的蛮力方法。但是时间复杂度是指数级的。有没有更好的算法？我的直觉是我们可以将节点权重转换为边权重，然后应用生成树算法。但是我无法清楚地解决它。如何解决这个问题？
编辑：看来我对子图的描述不够清楚。所选子图必须是单个连通分量。我希望现在清楚了。
我认为这个问题是 NP 难的，通过对斯坦纳树问题的归约。给定一个图 G 和一组需要跨越的节点 S，将 S 中所有节点的权重设置为 1，将所有其他节点设置为 0。节点权重至少为 |S| 的子图具有最小总边成本的树必须是一棵树（如果有任何循环，从循环中删除一条边只会降低成本）并且必须连接所有需要跨越的节点。因此它是一棵斯坦纳树。总的来说，这个减少可以在多项式时间内计算，所以你的问题是 NP-hard。