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

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

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)

Cites Work

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

Cited In (44)

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

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)