一般图上的限制性k node multi-multiway cut问题的启发式算法

Heuristic Algorithm for Restricted k Node Multi-multiway Cut Problem on Graph

限制性k node multi-multiway cut问题作为multiway cut问题的自然推广是NP难的。论文研究了一般图上的限制k node multi-multiway cut问题,首先用LP-relaxation和LP-rounding技术确定至少断开的k个终端集合,其次用改进的域增长技术将求得的分数解调整为整数解从而设计了该问题的一个启发式算法。

As a natural generalization of multiway cut problem,restricted k node multi-multiway cut problem is NP hard.This paper focuses on the problem of restricted k node multi-multiway cut problem on general graphs,first of all with LP-relaxation and LP-rounding technique to determine the disconnect at least k terminals,secondly with improved region growing technology will get score solution designed for integer solutions to the problem of a heuristic algorithm.