A greedy approximation for minimum connected dominating sets
From MaRDI portal
Publication:706637
DOI10.1016/j.tcs.2004.08.013zbMath1086.68106OpenAlexW1987990114WikidataQ60402914 ScholiaQ60402914MaRDI QIDQ706637
Lu Ruan, Weili Wu, Yingshu Li, Ker-I. Ko, Hongwei David Du, Xiao-Hua Jia
Publication date: 9 February 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.08.013
Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (32)
Minimum connected dominating sets and maximal independent sets in unit disk graphs ⋮ Greedy approximation for the minimum connected dominating set with labeling ⋮ Further results on the total monochromatic connectivity of graphs ⋮ New dominating sets in social networks ⋮ Two algorithms for minimum 2-connected \(r\)-hop dominating set ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ A greedy algorithm for the fault-tolerant connected dominating set in a general graph ⋮ A unified greedy approximation for several dominating set problems ⋮ Fault-tolerant total domination via submodular function approximation ⋮ A game theoretic approach for minimal connected dominating set ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ Nordhaus-Gaddum-type results on the connected edge domination number ⋮ Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem ⋮ Greed is good for deterministic scale-free networks ⋮ Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks ⋮ Wireless networking, dominating and packing ⋮ Computing Minimum k-Connected m-Fold Dominating Set in General Graphs ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ An exact algorithm for minimum CDS with shortest path constraint in wireless networks ⋮ TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET ⋮ Improving construction for connected dominating set with Steiner tree in wireless sensor networks ⋮ A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem ⋮ Some results for the two disjoint connected dominating sets problem ⋮ Construction of strongly connected dominating sets in asymmetric multihop wireless networks ⋮ Connected Domination ⋮ Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set ⋮ A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint ⋮ A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs ⋮ A PTAS for Weak Minimum Routing Cost Connected Dominating Set of Unit Disk Graph
Cites Work
This page was built for publication: A greedy approximation for minimum connected dominating sets
