Approximating minimum independent dominating sets in wireless networks
From MaRDI portal
Publication:975555
DOI10.1016/J.IPL.2008.09.021zbMATH Open1191.68866OpenAlexW2053372822MaRDI QIDQ975555FDOQ975555
Authors: Johann L. Hurink, Tim Nieberg 
Publication date: 9 June 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://research.utwente.nl/en/publications/approximating-minimum-independent-dominating-sets-in-wireless-networks(cceb6e65-6203-4c0e-bb0d-5c9d4fe76d7e).html
Recommendations
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
- MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
- Finding a maximal weighted independent set in wireless networks
- On approximating the minimum independent dominating set
- On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks
- On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm
Cites Work
- Unit disk graphs
- Unit disk graph recognition is NP-hard
- Approximating the minimum maximal independence number
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Simple heuristics for unit disk graphs
- Polynomial-time approximation schemes for packing and piercing fat objects
- Geometric ad-hoc routing
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Approximation and Online Algorithms
- Graph-Theoretic Concepts in Computer Science
- Robust algorithms for restricted domains
Cited In (12)
- MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
- Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Upper domination: complexity and approximation
- Maximum minimal vertex cover parameterized by vertex cover
- The secure metric dimension of the globe graph and the flag graph
- Approximation algorithms for intersection graphs
- MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
- The many facets of upper domination
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Maximum minimal vertex cover parameterized by vertex cover
This page was built for publication: Approximating minimum independent dominating sets in wireless networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q975555)
