多材料Terminal Steiner树拼接问题的近似算法研究

• 作者: 庞一成 文永松 朱淑娟
• 来源期刊: 现代电子技术
• 关键词: TerminalSteiner树 拼接问题 变尺寸装箱 近似算法 绝对近似比 时间复杂度
• 年，卷（期）: 2018,（10）
• 所属期刊栏目: 电子与信息器件
• 页码范围: 28-30
• 页数: 3页
• 分类号: TN911-34|TP301.6
• 语种: 中文
• DOI: 10.16652/j.issn.1004?373x.2018.10.007

摘要

在赋权连通网络下,给定多种材料及每种材料的费用和拼接费用,以便寻找赋权网络中的一棵Terminal Steiner树,并用给定材料连接此树,使得总费用及材料根数达到最小,记此问题为多材料Terminal Steiner树拼接问题.为了解决Terminal Steiner树拼接问题,首先分析Terminal Steiner 树拼接问题是NP问题,不存在多项式时间算法;然后基于Steiner 树问题和变尺寸装箱问题的近似算法及算法复杂度,给出多材料的Terminal Steiner树拼接问题的一个近似算法;最后证明算法的近似值及近似算法的时间复杂度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	庞一成	贵州财经大学数学与统计学院	13	11	2.0	2.0
2	朱淑娟	贵州财经大学数学与统计学院	5	2	1.0	1.0
3	文永松	贵州财经大学数学与统计学院	4	3	1.0	1.0