二部图中的最大赋权独立集
给定的二部图。每个顶点都有一些整数值-权重。 是否可以在多项式时间内找到此图中的最大权重independent vertex set？ 如果存在这样的解决方案，则此问题的算法是什么？ 推荐答案 在任何图中，独立集的补集都是vertex cover，反之亦然，所以你的问题等价于寻找图中最小权的顶点覆盖。后者可以使用最大流技术解决： 引入一个超源S和一个超宿T。通过以其权重为
..
independent-set相关内容
在树中找到最大独立集的算法
我需要一种算法来在树中找到最大独立集.我想从所有的叶子节点开始，然后删除这些叶子节点的直接父节点，然后选择我们删除的父节点的父节点，递归地重复这个过程，直到我们得到根.这是在 O(n) 时间内完成的吗?任何答复表示赞赏.谢谢. 谁能告诉我一个算法来找到树中的最大支配集. 解决方案 MAXIMUM INDEPENDENT SET 您可以通过树中的深度优先搜索来计算最大独立集.
..
使用贪婪算法寻找最小独立支配集
我开发了一种算法，该算法根据距离约束找到图的最小独立支配集.(我使用Python和NetworkX生成图并获取对) 该算法使用蛮力方法: 找到所有可能的边对 检查哪些节点满足距离约束 找到所有可能的独立支配集 比较找到的独立支配集并找到最小支配集 对于少量节点而言，这没有什么区别，但是对于大量节点，程序确实很慢. 有没有其他方法可以使它运行得更快? 谢谢
..
最大独立集合在Prolog中
我试图实现一个获取二叉树的Prolog谓词（表示为t（Left，Root，Right）），并返回一个列表，该列表是该树的最大独立集（MIS）及其大小。 我首先明白MIS（T）是具有root的MIS和没有root的MIS之间的最大值。 然后，我使用了两个定理，指出具有根的MIS是所有子树的没有根的MIS的统一，没有根的MIS是所有子树的MIS的统一。 ％mis是查找二叉树中最大独立集（MI
..
算法找到最大独立集在树上
我需要一个算法寻找一棵树最大独立设置。我从所有的叶子节点开始思考，然后删除直接父节点，这些叶节点，然后选择我们删除父节点的父节点，重复此过程递归，直到我们得到根。并在O（n）时间完成这件事？任何答复是AP preciated。谢谢。 和任何人都可以请点我一个算法来找出最大支配在树上设置。 解决方案 最大独立集 您可以计算通过树的深度优先搜索的最大独立集。 搜索将计算两个值在图中每个子树：
..