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

作者：杨惠娟; 胡晓飞; 段江梅

来源：贵阳学院学报(自然科学版), 2019, 14(04): 12-32.

DOI：10.16856/j.cnki.52-1142/n.2019.04.004

• k node multi-multiway cut问题
• 启发式算法
• LP-rounding技术
• LP-relaxation技术

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

• 单位
  昭通学院