Approximating minimum independent dominating sets in wireless networks

DOI10.1016/J.IPL.2008.09.021MaRDI QIDQ975555zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmsPTASminimum independent dominating setminimum maximal independent set

Mathematics Subject Classification ID

Approximation algorithms (68W25)

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

• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximating the minimum maximal independence number
• Approximation and Online Algorithms
• Geometric ad-hoc routing
• Graph-Theoretic Concepts in Computer Science
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Robust algorithms for restricted domains
• Simple heuristics for unit disk graphs
• Unit disk graph recognition is NP-hard
• Unit disk graphs

Cited in

(12)

• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
• Upper domination: complexity and approximation
• The many facets of upper domination
• MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• 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
• 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)