The relation of connected set cover and group Steiner tree

DOI10.1016/J.TCS.2012.02.035MaRDI QIDQ441864zbMATH OpenOpenAlexFDO

Authors Slobodan Jelić, Domagoj Matijević, Khaled 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

group Steiner treeset coverconnected set covercovering Steiner tree problemnode weighted group Steiner treeweighted connected set cover

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Approximation algorithms for the covering Steiner problem
• A simple approximation algorithm for minimum weight partial connected set cover
• scientific article; zbMATH DE number 5899242

Cites work

• scientific article; zbMATH DE number 219265 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• Approximating fault-tolerant group-Steiner problems
• Approximation algorithms for the covering Steiner problem
• Connected Set Cover Problem and Its Applications
• Online node-weighted Steiner tree and related problems
• Polylogarithmic inapproximability
• Requiring connectivity in the set covering problem

Cited in

(4)

• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• Approximation algorithms for minimum weight partial connected set cover problem
• A simple approximation algorithm for minimum weight partial connected set cover
• On the hardness of full Steiner tree problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q441864)