The relation of Connected Set Cover and Group Steiner Tree

被引：8
作者：
Elbassioni, Khaled [1 ]
Jelic, Slobodan [2 ]
Matijevic, Domagoj [2 ]
机构：
[1] Max Planck Inst Informat, Dept Algorithms & Complex 1, D-66123 Saarbrucken, Germany
[2] Josip Juraj Strossmayer Univ Osijek, Dept Math, Osijek 31000, Croatia
来源：
THEORETICAL COMPUTER SCIENCE | 2012年 / 438卷
关键词：
Set cover; Connected set cover; Weighted connected set cover; Group Steiner tree; Node weighted group Steiner tree; Covering Steiner tree problem;
D O I：
10.1016/j.tcs.2012.02.035
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We report that the Connected Set Cover (CSC) problem is just a special case of the Group Steiner Tree (GST) problem. Based on that we obtain the first algorithm for CSC with polylogarithmic approximation guarantee as well as the first approximation algorithms for the weighted version of the problem and the version with requirements. Moreover, we argue that the inapproximability result of GST will carry on to the weighted version of the CSC problem. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：96 / 101
页数：6
相关论文
共 12 条
  • [1] Probabilistic approximation of metric spaces and its algorithmic applications
    Bartal, Y
    [J]. 37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, : 184 - 193
  • [2] Requiring connectivity in the set covering problem
    Cerdeira, JO
    Pinto, LS
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2005, 9 (01) : 35 - 47
  • [3] Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233
  • [4] A survey and overview of habitat fragmentation experiments
    Debinski, DM
    Holt, RD
    [J]. CONSERVATION BIOLOGY, 2000, 14 (02) : 342 - 355
  • [5] A polylogarithmic approximation algorithm for the group Steiner tree problem
    Garg, N
    Konjevod, G
    Ravi, R
    [J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2000, 37 (01): : 66 - 84
  • [6] Halperin E, 2003, P 35 ANN ACM S THEOR, P585, DOI DOI 10.1145/780542.780628
  • [7] Khandekar Rohit, 2009, LEIBNIZ INT P INFORM, V4, P263
  • [8] Approximation algorithms for the covering Steiner problem
    Konjevod, G
    Ravi, R
    Srinivasan, A
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2002, 20 (03) : 465 - 482
  • [9] Online Node-weighted Steiner Tree and Related Problems
    Naor, Joseph
    Panigrahi, Debmalya
    Singh, Mohit
    [J]. 2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, : 210 - 219
  • [10] REICH G, 1990, LECT NOTES COMPUT SC, V411, P196
12