带禁区约束的直线上选址问题

• 作者: 丁巍 张固 陈光亭
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 选址问题 最小生成树 分治法 性能比
• 年，卷（期）: 2004,（4）
• 页码范围: 6-9
• 页数: 4页
• 分类号: O157.5
• 语种: 中文
• DOI: 10.3969/j.issn.1001-9146.2004.04.002

摘要

设欧氏平面上直线L的一侧有n个点的点集N,L上则有一个禁区集合F,现要在L上禁区集合以外找一点p,使得联结N∪{p}的最小网络之长达到最短.文章对这一问题提出了一个O(n2)的近似算法,其性能比为(√3/2).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈光亭	杭州电子科技大学理学院	44	74	5.0	7.0
2	丁巍	杭州电子科技大学理学院	2	12	1.0	2.0
3	张固	杭州电子科技大学理学院	2	12	1.0	2.0