A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem

DOI10.1007/s10878-014-9720-6zbMath1341.90118OpenAlexW2043377742MaRDI QIDQ5963614

Yaping Zhang, Yishuo Shi, Weili Wu, Zhao Zhang

Publication date: 23 February 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-014-9720-6

zbMATH Keywords

greedy algorithmfault-tolerant connected dominating setnon-submodular potential function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (8)

On approximating (connected) 2-edge dominating set by a tree ⋮ Further results on the total monochromatic connectivity of graphs ⋮ Optimal channel assignment with list-edge coloring ⋮ Construction of minimum edge-fault tolerant connected dominating set in a general graph ⋮ 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 ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ A greedy algorithm for the fault-tolerant outer-connected dominating set problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks
• Design and analysis of approximation algorithms
• A greedy approximation for minimum connected dominating sets
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• Approximation algorithms for connected dominating sets
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• Approximating Steiner Networks with Node-Weights

This page was built for publication: A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem