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

DOI10.1016/j.tcs.2008.11.005zbMath1162.68045OpenAlexW2040482710MaRDI QIDQ1006053

Xiaofeng Gao, Zhao Zhang, Weili Wu

Publication date: 17 March 2009

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

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

zbMATH Keywords

fault-toleranceconnected set coverreserve system

Mathematics Subject Classification ID

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

Related Items (8)

An approximation algorithm for maximum weight budgeted connected set cover ⋮ A heuristic approach for dividing graphs into bi-connected components with a size constraint ⋮ A simple approximation algorithm for minimum weight partial connected set cover ⋮ The relation of connected set cover and group Steiner tree ⋮ Wireless networking, dominating and packing ⋮ A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem' ⋮ Approximation algorithms for minimum weight partial connected set cover problem ⋮ Clustering with Internal Connectedness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Steiner tree problem with minimum number of Steiner points and bounded edge-length
• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• Requiring connectivity in the set covering problem
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• A quick method for finding shortest pairs of disjoint paths
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Connected Set Cover Problem and Its Applications
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
• Approximations for Steiner trees with minimum number of Steiner points

This page was built for publication: Algorithms for connected set cover problem and fault-tolerant connected set cover problem