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

A CONSTANT FACTOR APPROXIMATION FOR MINIMUM λ-edge-CONNECTED k-SUBGRAPH WITH METRIC COSTS

SIAM JOURNAL ON DISCRETE MATHEMATICS 2011年第3期25卷 1089-1102页

作者： Safari, Mohammadali Salavatipour, Mohammad R. Sharif Univ Technol Dept Comp Engn Tehran Iran Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

In the (k, lambda)-subgraph problem, we are given an undirected graph G = (V, E) with edge costs and two positive integers k and., and the goal is to find a minimum cost simple.-edge-connected subgraph of G with at least k nodes. This generalizes several classical problems, such as the minimum cost k-spanning tree problem, or k-MST (which is a (k, 1)-subgraph), and the minimum cost lambda-edge-connected spanning subgraph (which is a (vertical bar V(G)vertical bar, lambda)-subgraph). The only previously known results on this problem [L. C. Lau, J. S. Naor, M. R. Salavatipour, and M. Singh, SIAM J. Comput., 39 (2009), pp. 1062-1087], [C. Chekuri and N. Korula, in Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Bangalore, India, LIPIcs 2, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik, Dagstuhl, Germany, 2008, pp. 119-130] show that the (k, 2)-subgraph problem has an O(log(2) n)-approximation (even for 2-node-connectivity) and that the (k, lambda)-subgraph problem in general is almost as hard as the densest k-subgraph problem. In this paper we show that if the edge costs are metric (i.e., satisfy the triangle inequality), like in the k-MST problem, then there is an O(1)-approximation algorithm for the (k, lambda)-subgraph problem. This essentially generalizes the k-MST constant factor approximability to higher connectivity.

关键词： approximation algorithm lambda-edge-connectivity k-subgraph metric cost

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：