检索结果-南通市图书馆

Approximation Algorithms for Solving the 1-line minimum Steiner tree of line segments Problem

Journal of the Operations Research Society of China 2024年第3期12卷 729-755页

作者： Jian-Ping Li Su-Ding Liu Jun-Ran Lichen Peng-Xiang Pan Wen-Cheng Wang Department of Mathematics Yunnan UniversityKunming650504YunnanChina School of Mathematics and Physics Beijing University of Chemical TechnologyBeijing650504China

We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)***,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner ***,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)*** addition,when two endpoints of each edge in Eo need to be located on two different line segments in S,respectively,we refer to that problem as the minimum spanning tree of line segments(MST-LS)*** obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)to solve the MST-LS problem;(2)we show that the algorithm designed in(1)is a 1.214-approximation algorithm to solve the MStT-LS problem;(3)using the combination of the algorithm designed in(1)as a subroutine for many times,a technique of finding linear facility location and a key lemma proved by techniques of computational geometry,we present a 1.214-approximation algorithm in time O(n^(3) log n)to solve the 1L-MStT-LS problem.

关键词： 1-line minimum Steiner tree of line segments minimum spanning tree of line segments Voronoi diagram of line segments Steiner ratio Approximation algorithms

来源：

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：