The relation of connected set cover and group Steiner tree

DOI10.1016/j.tcs.2012.02.035zbMath1246.05148OpenAlexW2020427431MaRDI QIDQ441864

Slobodan Jelić, Domagoj Matijević, Khaled M. Elbassioni

Publication date: 8 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.035

zbMATH Keywords

set covergroup Steiner treeconnected set covercovering Steiner tree problemnode weighted group Steiner treeweighted connected set cover

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

A simple approximation algorithm for minimum weight partial connected set cover ⋮ On the hardness of full Steiner tree problems ⋮ Approximation algorithms for minimum weight partial connected set cover problem ⋮ Approximation algorithms for the connected sensor cover problem

Cites Work

• Unnamed Item
• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• Requiring connectivity in the set covering problem
• Approximating Fault-Tolerant Group-Steiner problems
• Polylogarithmic inapproximability
• A Greedy Heuristic for the Set-Covering Problem
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Approximation algorithms for the covering Steiner problem
• Connected Set Cover Problem and Its Applications
• Online Node-Weighted Steiner Tree and Related Problems

This page was built for publication: The relation of connected set cover and group Steiner tree