将图划分为k个非空块-最大化

Question

我正在寻找算法(链接/名称就足够了)将图划分为k(在我的例子中是2-4)非空块，这样总边权之和(每个块的和权)是最大的。我知道这个问题可能在NP类中，但是我有少量的顶点(8-15)，图是稠密且连通的。边缘权重可能为负值。

Answer 1

考虑到实例的规模很小，动态编程应该运行得很好。

这样做的目的是建立一个由对组成的表，该表由一个从j到0到k的数字和一个顶点集S组成。当将S诱导的子图划分为j片段时，表的值是片内边权的最大和。我们有一个重复

T[0, {}] = 0
T[0, S] such that S ≠ {} = -infinity
T[j, S] such that j > 0 = max over subsets T of S of value(T) + T[j - 1, S - T],

其中，value(T)是由顶点T集合导出的片内边缘权重之和。运行时间为O(n^2 3^n)，其中n为顶点数。假定只保存表T的当前行和前一行，空间使用为T。

我预计这种方法在C中的实际运行时间为n= 15和k= 4，假设良好的位集执行，在普通硬件上仅为一秒。