Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
From MaRDI portal
Publication:1755744
DOI10.1007/s00453-017-0385-2zbMath1414.05224arXiv1511.09156OpenAlexW2964201857MaRDI QIDQ1755744
Publication date: 11 January 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.09156
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Signed and weighted graphs (05C22)
Related Items (6)
Approximating \(k\)-connected \(m\)-dominating sets ⋮ Approximating k-Connected m-Dominating Sets ⋮ A polylogarithmic approximation algorithm for 2-edge-connected dominating set ⋮ 2-node-connectivity network design ⋮ Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems ⋮ 2-node-connectivity network design
Cites Work
- Unnamed Item
- New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
- Node-weighted Steiner tree approximation in unit disk graphs
- On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
- Unit disk graphs
- Approximation algorithms for connected dominating sets
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- On the approximability and exact algorithms for vector domination and related problems in graphs
- Latency-bounded target set selection in social networks
- On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
- Approximating minimum-cost connectivity problems via uncrossable bifamilies
- Weighted geometric set multi-cover via quasi-uniform sampling
- Prize-Collecting Survivable Network Design in Node-Weighted Graphs
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- Simple heuristics for unit disk graphs
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Spider covers for prize-collecting network activation problem
- Steiner Tree Approximation via Iterative Randomized Rounding
- A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
This page was built for publication: Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
