中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 数学与系统科学研究院
  3. 中国科学院数学与系统科学研究院
  4. 博士后
On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane R-2

文献类型：期刊论文

作者Li, Jianping1; Zheng, Yujie1; Lichen, Junran1,2; Wang, Wencheng1
刊名OPTIMIZATION LETTERS
出版日期2020-08-10
页码15
关键词A fixed linel Steiner tree Steiner points Delaunay triangulation Approximation algorithms
ISSN号1862-4472
DOI10.1007/s11590-020-01627-7
英文摘要In this paper, we address the problem of minimum number of Steiner points of constrained 1-line-fixed Steiner tree (abbreviated to the MNSP-C1LF-ST problem), which is defined as follows. Given n terminals located at the same side of a fixed line l in the Euclidean plane R-2 and a constant L, we are asked to find a Steiner tree T to interconnect these n terminals in R-2 such that the Steiner points of the tree T, which has at least one Steiner point, are all located on the fixed line l and that the weight w(T) = Sigma(e is an element of T) w(e) <= L, the objective is to minimize the number s(T) of Steiner points of the tree T, where the weight w(e) = 0 if the two endpoints of that edge e is an element of T are located on the line l and otherwise the weight w(e) is the Euclidean distance between the two endpoints of that edge e is an element of T. In addition, when L is the minimum weight of all possible constrained 1-line-fixed Steiner trees as mentioned above, we refer to this version as the problem of minimum number of Steiner points of constrained 1-line-fixed minimum Steiner tree (abbreviated to the MNSP-C1LF-MST problem). We obtain two main results. (1) Using strategies of finding a minimum spanning tree with a degree constraint, we can design a 3-approximation algorithm in time O(n(2) log n) to solve the MNSP-C1LF-ST problem. (2) Combining Delaunay triangulation properties and strategies of finding a minimum spanning tree with a degree constraint, we can provide a simple exact algorithm in time O(n log n log beta(n)) to solve the MNSP-C1LF-MST problem, where beta(n) = min{i vertical bar log(i) n <= 4 - 6/n}.
资助项目Project of the National Natural Science Foundation of China[11861075] ; Project of the National Natural Science Foundation of China[11801498] ; Project for Innovation Team (Cultivation) of Yunnan Province, Joint Key Project of Yunnan Provincial Science and Technology Department and Yunnan University[2018FY001014] ; IRTSTYN ; Project of Doctorial Fellow Award of Yunnan Province[2018010514]
WOS研究方向Operations Research & Management Science ; Mathematics
语种英语
WOS记录号WOS:000557748500001
出版者SPRINGER HEIDELBERG
源URL[http://ir.amss.ac.cn/handle/2S8OKBNM/51970]  
专题博士后
通讯作者Li, Jianping
作者单位1.Yunnan Univ, Dept Math, Kunming 650504, Yunnan, Peoples R China
2.Acad Math & Syst Sci, Inst Appl Math, Beijing 100190, Peoples R China
推荐引用方式
GB/T 7714		 Li, Jianping,Zheng, Yujie,Lichen, Junran,et al. On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane R-2[J]. OPTIMIZATION LETTERS,2020:15.
APA Li, Jianping,Zheng, Yujie,Lichen, Junran,&Wang, Wencheng.(2020).On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane R-2.OPTIMIZATION LETTERS,15.
MLA Li, Jianping,et al."On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane R-2".OPTIMIZATION LETTERS (2020):15.

入库方式： OAI收割

来源：数学与系统科学研究院

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。