K条路的两个问题

• 作者: 张同全 王泽磊
• 来源期刊: 云南民族大学学报（自然科学版）
• 学科: 数学
• 关键词: 最小费用流 k条路 偏差算法
• 年，卷（期）: 2005,（2）
• 页码范围: 147-148,150
• 页数: 3页
• 分类号: O157.5
• 字数: 2220字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-8513.2005.02.014

摘要

关于寻找有向连通图G=(V,E)的最小最大的k条弧不交路的问题是NP-完备的.研究这个问题的推广--有容量限制的k条路问题:①寻找k条路,使得k条路的费用之和尽可能小;②寻找k条路,使得k条路中最长的路的费用尽可能小.给出了问题①的一个最优算法,其复杂度为O(k| V|2),同时证明了该算法对于问题是k-近似的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张同全	云南大学数学系	8	16	3.0	3.0
2	王泽磊	云南大学数学系	3	4	1.0	2.0