Halin图上求解最大切割问题的高效算法

• 作者: 娄定俊 秦宗蓉 蒋一帆 许莉
• 来源期刊: 中山大学学报（自然科学版）
• 学科: 数学
• 关键词: 最大切割问题 可扩性 收缩扇 奇面
• 年，卷（期）: 2019,（4）
• 页码范围: 90-98
• 页数: 9页
• 分类号: O157.5
• 字数: 6886字
• 语种: 中文
• DOI: 10.13471/j.cnki.acta.snus.2019.04.009

摘要

对于一个给定的带权图G=(V,E),和一个正整数k,是否存在一种切割方法,将V划分成两个不相交的子集V1和V2,使得所有一个端点在V1中,另一个端点在V2中的边的权相加之和大于等于k?该问题是在普通图上的一个NPC问题,称为最大切割问题.当各边的权为1时,该问题在普通图上仍是一个NPC问题.提出了一个算法,用于在Halin图上解决最大切割问题,该算法时间复杂度为O(n),其中n=V(G).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	娄定俊	中山大学数据科学与计算机学院	5	15	3.0	3.0
2	许莉	中山大学数据科学与计算机学院	1	0	0.0	0.0
3	蒋一帆	中山大学数据科学与计算机学院	1	0	0.0	0.0
4	秦宗蓉	中山大学数据科学与计算机学院	1	0	0.0	0.0