On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane R-2

doi:10.1007/s11590-020-01627-7

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 博士后

	On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane R-2
	Li, Jianping 1; Zheng, Yujie 1; Lichen, Junran 1,2; Wang, Wencheng 1
刊名	OPTIMIZATION LETTERS
	2020-08-10
页码	15
关键词	A fixed linel Steiner tree Steiner points Delaunay triangulation Approximation algorithms
ISSN号	1862-4472
DOI	10.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
语种	英语
出版者	SPRINGER HEIDELBERG
WOS记录号	WOS:000557748500001
内容类型	期刊论文
源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.