关于哈密顿轨问题最小流模型的讨论

• 作者: 宁宣熙
• 来源期刊: 南京航空航天大学学报（英文版）
• 学科: 社会科学
• 关键词: 图论 哈密顿轨 生成流
• 年，卷（期）: 2004,（4）
• 页码范围: 322-325
• 页数: 4页
• 分类号: C931
• 字数: 359字
• 语种: 英文
• DOI: 10.3969/j.issn.1005-1120.2004.04.015

摘要

Mason Iri论证了网络最小流问题可以在多项式时间内转换为哈密顿问题的模型与方法.本文利用一个反例指出了在该证明中使用的模型存在有不严格的地方.在此基础上,利用网络最小生成流的概念提出了一个修正模型,并证明了无环最小生成流问题可以在多项式时间内转换为哈密顿圈问题.文中最后指出,这一新的模型为解决在有向图内构造哈密顿轨的有效算法提供了一个新的思路和方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宁宣熙	南京航空航天大学经济管理学院	204	2932	27.0	42.0