Sas*_*ank 6 algorithm graph time-complexity graph-algorithm
我遇到了这个问题 - 在一个无向图中,每个节点和边都有一个权重.所有权重都是非负的.给定值S,找到具有最小边权重和的连通子图,使得其节点权重之和至少为S.
最明显的解决方案是考虑所有可能的子图的蛮力方法.但时间复杂度是指数级的.有没有更好的算法呢？我的直觉是我们可以将节点权重转换为边权重,然后应用生成树算法.但我无法清楚地解决它.如何解决这个问题呢？
编辑:看起来我对子图的描述不够清楚.选定的子图必须是单个连接的组件.我希望现在很清楚.
我认为这个问题是 NP 困难的，通过斯坦纳树问题的简化。给定一个图G和一组需要跨越的节点S，将S中所有节点的权重设置为1，将所有其他节点设置为0。节点权重至少为|S|的子图 总边成本最小的必须是一棵树（如果有环，从环中删除边只会降低成本）并且必须连接所有需要跨越的节点。因此它是一棵斯坦纳树。总的来说，这种减少可以在多项式时间内计算出来，所以你的问题是 NP 困难的。