Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set
From MaRDI portal
Publication:5131722
DOI10.1287/ijoc.2017.0775OpenAlexW2796249649MaRDI QIDQ5131722
Zhao Zhang, Jiao Zhou, Ding-Zhu Du, Shaojie Tang, Xiao-hui Huang
Publication date: 9 November 2020
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/ijoc.2017.0775
Related Items
Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage ⋮ Connected domination in maximal outerplanar graphs
Cites Work
- Unnamed Item
- Unnamed Item
- A greedy algorithm for the fault-tolerant connected dominating set in a general graph
- New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
- A greedy approximation for minimum connected dominating sets
- Node-weighted Steiner tree approximation in unit disk graphs
- Solving connected dominating set faster than \(2^n\)
- 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
- A better constant-factor approximation for weighted dominating set in unit disk graph
- A short note on the approximability of the maximum leaves spanning tree problem
- Approximation algorithms for connected dominating sets
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
- An improved LP-based approximation for steiner tree
- Dual-Based Local Search for the Connected Facility Location and Related Problems
- Approximating minimum-cost connectivity problems via uncrossable bifamilies
- Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
- An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets
- Spanning Trees with Many Leaves
- A PTAS for the Weighted Unit Disk Cover Problem
- A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- Steiner Tree Approximation via Iterative Randomized Rounding
- A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
