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

On the minimum corridor connection problem and other generalized geometric problems

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2009年第9期42卷 939-951页

作者： Bodlaender, Hans L. Feremans, Corinne Grigoriev, Alexander Penninkx, Eelko Sitters, Rene Wolle, Thomas Maastricht Univ Dept Quantitat Econ NL-6200 MD Maastricht Netherlands Univ Utrecht Inst Informat & Comp Sci NL-3508 TB Utrecht Netherlands Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands NICTA Sydney Alexandria NSW 1435 Australia

In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into "rooms", one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Minimum corridor connection generalized geometric problems Complexity Exact algorithms Approximations

来源：评论

学校读者我要写书评

暂无评论

On the minimum corridor connection problem and other generalized geometric problems

On the minimum corridor connection problem and other general...

引用

European Workshop on Computational Geometry

关键词： Minimum corridor connection generalized geometric problems Complexity Exact algorithms Approximations

来源：评论

学校读者我要写书评

暂无评论

On the minimum corridor connection problem and other generalized geometric problems

On the minimum corridor connection problem and other general...

引用

4th International Workshop on Approximation and Online Algorithms

作者： Bodlaender, Hans Feremans, Corinne Grigoriev, Alexander Penninkx, Eelko Sitters, Rene Wolle, Thomas Univ Utrecht Inst Informat & Comp Sci POB 80-089 NL-3508 TB Utrecht Netherlands Maastricht Univ Dept Quantitat Econ NL-6200 MD Maastricht Netherlands Max Planck Inst Comp Sci Dept Algorithms & Complex D-66123 Saarbrucken Germany Natl ICT Australia Ltd Alexandria NSW 1435 Australia

ISBN: (纸本)9783540695134

In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into "rooms", one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give an subexponential time exact algorithm. For the special case of k-outerplanar graphs the running time becomes O(n(3)). We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.

关键词： minimum corridor connection generalized geometric problems complexity exact algorithms approximations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：