检索结果-内蒙古大学图书馆

Approximating Spanning Trees with Few Branches

THEORY OF COMPUTING SYSTEMS 2015年第1期56卷 181-196页

作者： Chimani, Markus Spoerhase, Joachim Univ Jena Inst Comp Sci Jena Germany Univ Wurzburg Inst Comp Sci D-97070 Wurzburg Germany

Given an undirected, connected graph, the aim of the minimum branch-node spanning tree problem is to find a spanning tree with the minimum number of nodes of degree larger than 2. The problem is motivated by network design problems where junctions are significantly more expensive than simple end- or through-nodes, and are thus to be avoided. Unfortunately, it is NP-hard to recognize instances that admit an objective value of zero, rendering the search for guaranteed approximation ratios futile. We suggest to investigate a complementary formulation, called maximum path-node spanning tree, where the goal is to find a spanning tree that maximizes the number of nodes with degree at most two. While the optimal solutions (and the practical applications) of both formulations coincide, our formulation proves more suitable for approximation. In fact, it admits a trivial 1/2-approximation algorithm. Our main contribution is a local search algorithm that guarantees a ratio of 6/11, as well as showing that the problem is APX-hard, i.e., it does not allow a PTAS.

关键词： Theory of computation Design and analysis of algorithms approximation algorithms analysis Routing and network design problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：