A greedy approximation for minimum connected dominating sets

DOI10.1016/J.TCS.2004.08.013zbMATH Open1086.68106OpenAlexW1987990114WikidataQ60402914 ScholiaQ60402914MaRDI QIDQ706637FDOQ706637

Authors Lu Ruan, Weili Wu, Yingshu Li, Hongwei Du, X.-H. Jia, Ker-I Ko 

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

zbMATH Keywords

greedy approximationConnected dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• A unified greedy approximation for several dominating set problems
• Minimum connected dominating sets in finite graphs
• Approximation algorithms for connected dominating sets
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximation algorithms for connected dominating sets

Cites work

• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximation algorithms for connected dominating sets
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• `` Strong NP-Completeness Results

Cited in

(44)

• A greedy algorithm for the fault-tolerant outer-connected dominating set problem
• Max-leaves spanning tree is APX-hard for cubic graphs
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Revisiting connected dominating sets: an optimal local algorithm?
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• Greedy approximation for the minimum connected dominating set with labeling
• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• Approximation algorithm for (connected) Italian dominating function
• Some results for the two disjoint connected dominating sets problem
• Fault-tolerant total domination via submodular function approximation
• Two algorithms for minimum 2-connected \(r\)-hop dominating set
• Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems
• Approximating \(k\)-connected \(m\)-dominating sets
• Nordhaus-Gaddum-type results on the connected edge domination number
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• Greed is good for deterministic scale-free networks
• In Memoriam: Ker-I Ko (1950–2018)
• Connected dominating set in hypergraph
• An exact algorithm for minimum CDS with shortest path constraint in wireless networks
• Minimum connected dominating sets in finite graphs
• Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks
• A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets
• Revisiting connected dominating sets: an almost optimal local information algorithm
• Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem
• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• Wireless networking, dominating and packing
• Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set
• A game theoretic approach for minimal connected dominating set
• The \(k\)-hop connected dominating set problem: approximation and hardness
• Approximation algorithms for connected dominating sets
• A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
• Efficient local search based on dynamic connectivity maintenance for minimum connected dominating set
• New dominating sets in social networks
• Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs
• Connected domination
• Analysis of a greedy heuristic for finding small dominating sets in graphs
• Construction of strongly connected dominating sets in asymmetric multihop wireless networks
• A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
• A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
• A PTAS for weak minimum routing cost connected dominating set of unit disk graph
• Further results on the total monochromatic connectivity of graphs
• A unified greedy approximation for several dominating set problems

This page was built for publication: A greedy approximation for minimum connected dominating sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q706637)