The relation of connected set cover and group Steiner tree

Khaled Elbassioni; Slobodan Jelić; Domagoj Matijević

doi:10.1016/j.tcs.2012.02.035

The relation of connected set cover and group Steiner tree

Khaled Elbassioni, Slobodan Jelić, Domagoj Matijević

Electrical Engineering

J. J. Strossmayer University of Osijek

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

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.

Original language	British English
Pages (from-to)	96-101
Number of pages	6
Journal	Theoretical Computer Science
Volume	438
DOIs	https://doi.org/10.1016/j.tcs.2012.02.035
State	Published - 22 Jun 2012

Keywords

Connected set cover
Covering Steiner tree problem
Group Steiner tree
Node weighted group Steiner tree
Set cover
Weighted connected set cover

Access to Document

10.1016/j.tcs.2012.02.035

Cite this

@article{d3a449f0b3a94624a368faf9fc14f0b4,

title = "The relation of connected set cover and group Steiner tree",

abstract = "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.",

keywords = "Connected set cover, Covering Steiner tree problem, Group Steiner tree, Node weighted group Steiner tree, Set cover, Weighted connected set cover",

author = "Khaled Elbassioni and Slobodan Jeli{\'c} and Domagoj Matijevi{\'c}",

year = "2012",

month = jun,

day = "22",

doi = "10.1016/j.tcs.2012.02.035",

language = "British English",

volume = "438",

pages = "96--101",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - The relation of connected set cover and group Steiner tree

AU - Elbassioni, Khaled

AU - Jelić, Slobodan

AU - Matijević, Domagoj

PY - 2012/6/22

Y1 - 2012/6/22

N2 - 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.

AB - 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.

KW - Connected set cover

KW - Covering Steiner tree problem

KW - Group Steiner tree

KW - Node weighted group Steiner tree

KW - Set cover

KW - Weighted connected set cover

UR - http://www.scopus.com/inward/record.url?scp=84861189290&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2012.02.035

DO - 10.1016/j.tcs.2012.02.035

M3 - Article

AN - SCOPUS:84861189290

SN - 0304-3975

VL - 438

SP - 96

EP - 101

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

The relation of connected set cover and group Steiner tree

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this