如何仅使用有限数量的节点（例如 N 个节点）从图中找到最大边数。选定的边使用它的两侧。
问问题
109 次
1 回答
1
一个已知的问题。听起来好像您的问题被称为k 密集子图问题（您的 N 扮演 k 的角色）。
坏消息：这个问题被认为是 NP 难的，即使你的 IP 都没有出现超过 3 次或者输入图是二分的。您是否知道图表的任何其他特殊属性？
更多坏消息：快速浏览最近的文献，似乎连具有良好误差界限的算法都没有现成的可用。在我看来，即使“只有”100 个输入节点，问题也可能很糟糕。
祝你好运！
于 2012-05-30T22:49:32.693 回答