一种求解最小割集问题的新思路

• 作者: 卢志渊 季桂树 李庆春
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 最小割集 最大流 算法
• 年，卷（期）: 2003,（2）
• 所属期刊栏目: 学术探讨
• 页码范围: 98-100
• 页数: 3页
• 分类号: TP301.6
• 字数: 3372字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2003.02.034

摘要

从本质上来说,最小割集问题与最大流问题是同一个问题.由于后者的实用性更强,人们对它投入的关注与研究也更多,因而实际中是通过最大流问题来求最小割集问题.最大流-最小割集定理给出了一种用最大流算法求最小割集问题的方法,但在实际应用中,这种方法有时显得繁冗并有些迂回.文章首先介绍了最大流、最小割集的相关概念,然后从实际应用出发提出了一种用最大流求流图最小割集的新算法.随后证明了该算法的正确性,并举例说明了这种算法思想在其它方面的应用.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	季桂树	中南大学信息工程学院	32	288	8.0	16.0
2	卢志渊	中南大学信息工程学院	3	24	2.0	3.0
3	李庆春	中南大学信息工程学院	3	68	2.0	3.0