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

• 作者: 杨惠娟 段江梅 胡晓飞
• 来源期刊: 贵阳学院学报（自然科学版）
• 学科: 数学
• 关键词: k node multi-multiway cut问题 启发式算法 LP-rounding技术 LP-relaxation技术
• 年，卷（期）: 2019,（4）
• 所属期刊栏目: 基础理论研究
• 页码范围: 12-15,32
• 页数: 5页
• 分类号: O157.5
• 字数: 4496字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-6125.2019.04.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡晓飞	昭通学院数学与统计学院	32	46	4.0	4.0
2	杨惠娟	昭通学院数学与统计学院	19	17	3.0	3.0
3	段江梅	昭通学院数学与统计学院	10	1	1.0	1.0