Algorithms for connected set cover problem and fault-tolerant connected set cover problem

被引：20

作者：

Zhang, Zhao ^{[1
]}

Gao, Xiaofeng ^{[2
]}

Wu, Weili ^{[2
]}

机构：

[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China

[2] Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75080 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2009年 / 410卷 / 8-10期

基金：

美国国家科学基金会;

关键词：

Reserve system; Connected set cover; Fault-tolerant; MINIMUM NUMBER; STEINER TREES; SELECTION;

D O I：

10.1016/j.tcs.2008.11.005

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a set V of elements, S a family of subsets of V, and G a connected graph on vertex set S,a connected set cover (CSC) is a subfamily R of S such that every element in V is covered by at least one set of R, and the subgraph G[R] of G induced by R is connected. If furthermore G[R] is k-connected and every element in V is covered by at least m sets in R, then R is a (k, m)-CSC. In this paper, we present two approximation algorithms for the minimum CSC problem, and one approximation algorithm for the minimum (2, m)-CSC problem. Performance ratios are analyzed. These are the first approximation algorithms for CSC problems in general graphs with guaranteed performance ratios. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：812 / 817

页数：6

共 23 条

[1] [Anonymous], Introduction to algorithms
[2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[3] Ausiello G., 2003, Complexity and approximation: Cominatorial optimization problems and their approximality properties
[4] Incorporating connectivity into reserve selection procedures
Briers, RA
[J]. BIOLOGICAL CONSERVATION, 2002, 103 (01) : 77 - 83
[5] Requiring connectivity in the set covering problem
Cerdeira, JO
Pinto, LS
[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2005, 9 (01) : 35 - 47
[6] Approximations for Steiner trees with minimum number of Steiner points
Chen, DH
Du, DZ
Hu, XD
Lin, GH
Wang, LS
Xue, GL
[J]. THEORETICAL COMPUTER SCIENCE, 2001, 262 (1-2) : 83 - 99
[7] A survey and overview of habitat fragmentation experiments
Debinski, DM
Holt, RD
[J]. CONSERVATION BIOLOGY, 2000, 14 (02) : 342 - 355
[8] Du DZ, 2001, LECT NOTES COMPUT SC, V2108, P509
[9] Feige U., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P314, DOI 10.1145/237814.237977
[10] Improved methods for approximating node weighted Steiner trees and connected dominating sets
Guha, S
Khuller, S
[J]. INFORMATION AND COMPUTATION, 1999, 150 (01) : 57 - 74

← 1 2 3 →