如何以输入（n，顶点数）的大小在多项式时间内找到二分法？可能吗？顶点的数量必须保持不变，您可以删除尽可能少的边。多项式时间是指 O(n)、O(n^2) 还是 O(n)？
我会做一个 BFS 将节点放在两个不同的集合中，但复杂度会是 O(V+E)，这不是我想要的。
有什么建议么？谢谢你。
问问题
97 次
1 回答
0
最佳解决方案通常是NP-hard，但存在大量多项式启发式。看一下Kernighan-Lin的简单算法。
如果您尝试解决实际问题而不是家庭作业，则最好搜索预先存在的分区器。有许多库可用，特别是在 METIS 系列中。
于 2013-11-05T08:10:26.850 回答