A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS

DOI10.1142/S0129054103001753zbMath1075.68066MaRDI QIDQ5696912

Ophir Frieder, Khaled M. Alzoubi, Peng-Jun Wan

Publication date: 19 October 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmminorconnected dominating set2-independent set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

Experiments on data reduction for optimal domination in networks ⋮ Computational study on planar dominating set problem ⋮ Capacitated domination: problem complexity and approximation algorithms

Cites Work

• Unnamed Item
• Unit disk graphs
• Approximation algorithms for connected dominating sets
• Approximation algorithms for NP-complete problems on planar graphs
• On the hardness of approximating minimization problems
• Simple heuristics for unit disk graphs

This page was built for publication: A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS