Approximation algorithms for highly connected multi-dominating sets in unit disk graphs

DOI10.1007/S00453-017-0385-2MaRDI QIDQ1755744zbMATH OpenOpenAlexFDO

Authors Takuro Fukunaga

Publication date 11 January 2019

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.09156

zbMATH Keywords

approximation algorithmconnected dominating setunit disk graph

Mathematics Subject Classification ID

Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Abstract: Given an undirected graph on a node set $V$ and positive integers $k$ and $m$, a $k$-connected $m$-dominating set ($(k,m)$-CDS) is defined as a subset $S$ of $V$ such that each node in $VsetminusS$ has at least $m$ neighbors in $S$, and a $k$-connected subgraph is induced by $S$. The weighted $(k,m)$-CDS problem is to find a minimum weight $(k,m)$-CDS in a given node-weighted graph. The problem is called the unweighted $(k,m)$-CDS problem if the objective is to minimize the cardinality of a $(k,m)$-CDS. These problems have been actively studied for unit disk graphs, motivated by the application of constructing a virtual backbone in a wireless ad hoc network. However, constant-approximation algorithms are known only for $kleq3$ in the unweighted $(k,m)$-CDS problem, and for $(k,m)=(1,1)$ in the weighted $(k,m)$-CDS problem. In this paper, we consider the case in which $mgeqk$, and we present a simple $O(5^{k}k!)$-approximation algorithm for the unweighted $(k,m)$-CDS problem, and a primal-dual $O(k^{2}logk)$-approximation algorithm for the weighted $(k,m)$-CDS problem. Both algorithms achieve constant approximation factors when $k$ is a fixed constant.

Recommendations

• Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• Approximating \(k\)-connected \(m\)-dominating sets
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

Cites work

• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for connected dominating sets
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Latency-bounded target set selection in social networks
• 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 constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• On the approximability and exact algorithms for vector domination and related problems in graphs
• Prize-collecting survivable network design in node-weighted graphs
• Simple heuristics for unit disk graphs
• Spider covers for prize-collecting network activation problem
• Steiner tree approximation via iterative randomized rounding
• Unit disk graphs
• Weighted geometric set multi-cover via quasi-uniform sampling

Cited in

(13)

• Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• Approximating \(k\)-connected \(m\)-dominating sets
• 2-node-connectivity network design
• Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
• On the power of lookahead in greedy scheme for finding a minimum CDS for unit disk graphs
• Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
• A polylogarithmic approximation algorithm for 2-edge-connected dominating set
• Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
• Approximating k-Connected m-Dominating Sets
• 2-node-connectivity network design

This page was built for publication: Approximation algorithms for highly connected multi-dominating sets in unit disk graphs

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