A Simpler Constant Factor Approximation for the k-Connected m-Domination Set Problem in Unit Disk Graph
| Autor: | Yingshu Li, Bei Liu, Sung-Sik Kwon, Wei Wang, Donghyun Kim |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Mathematical optimization Wireless network Computer science Unit disk graph Approximation algorithm 020206 networking & telecommunications 02 engineering and technology Unit disk Graph Constant factor Dominating set 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing |
| Zdroj: | ICCCN |
| DOI: | 10.1109/icccn.2016.7568483 |
| Popis: | Over years, many efforts are made for the problem of constructing fault-tolerant virtual backbones in wireless network. In case that the wireless network consists of physically equivalent nodes, e.g. with the same communication range, unit disk graph model is universally used to abstract the wireless network and the problem is defined as the $k$-connected $m$- dominating set problem on the unit disk graph. As this problem is NP-hard, the design and analysis of an approximation algorithm for the problem is of great theory interest. To the best of our knowledge, there has been no officially published work which introduces a constant factor approximation algorithm for the $k$-connected $m$-dominating set problem where $k$ and $m$ can be arbitrary pair of positive integers, and the existing literatures are presenting only partial solutions, e.g. works only under the condition that $m \geq k \geq 1$ and $k \leq 3$. In this paper, we introduce a new constant factor algorithm to compute the minimum $k$- connected $m$-dominating set problem in unit disk graphs, which works with arbitrary pair of positive integers $k$ and $m$ which are satisfying the condition $m \geq k \geq 1$. This algorithm is based on the decomposition of the graph and is completely different from any known strategies, official ones as well as unofficial ones, and we provide theoretical analysis to prove that the approximation ratio is constant. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|