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

论文摘要

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

论文目录

• 1 算法详述
•   1.1 初步切割
•   1.2 收缩扇
•   1.3 最大切割
• 2 算法分析
•   2.1 算法正确性证明
•     ① 对轮分情况讨论如下:
•     ② 对扇的情形讨论如下:
•   2.2 时间复杂度分析

文章来源

类型: 期刊论文

作者: 许莉,娄定俊,蒋一帆,秦宗蓉

关键词: 最大切割问题,可扩性,收缩扇,奇面

来源: 中山大学学报(自然科学版) 2019年04期

年度: 2019

分类: 基础科学

专业: 数学

单位: 中山大学数据科学与计算机学院

基金: 广东省自然科学基金(2016A030313829)

分类号: O157.5

DOI: 10.13471/j.cnki.acta.snus.2019.04.009

页码: 90-98

总页数: 9

文件大小: 2490K

下载量: 31