Approximating k-Connected m-Dominating Sets
From MaRDI portal
Publication:5874545
DOI10.4230/LIPIcs.ESA.2020.73OpenAlexW3081528035MaRDI QIDQ5874545
Publication date: 7 February 2023
Full work available at URL: https://doi.org/10.4230/LIPIcs.ESA.2020.73
approximation algorithm\(k\)-connected graph\(m\)-dominating setsubset \(k\)-connectivityrooted subset \(k\)-connectivity
Related Items
Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges, 2-node-connectivity network design
Cites Work
- Unnamed Item
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- Approximating source location and star survivable network problems
- New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
- Node-weighted Steiner tree approximation in unit disk graphs
- Unit disk graphs
- Approximation algorithms for connected dominating sets
- Approximating node connectivity problems via set covers
- Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
- Independence free graphs and vertex connectivity augmentation
- Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- On the optimal vertex-connectivity augmentation
- Approximating subset \(k\)-connectivity problems
- On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
- Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
- Approximating Minimum-Cost $k$-Node Connected Subgraphs via Independence-Free Graphs
- Approximating minimum-cost connectivity problems via uncrossable bifamilies
- 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
- Erratum
- Spider Covers for Prize-Collecting Network Activation Problem
- Simple heuristics for unit disk graphs
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
- A 4 + ε approximation for k-connected subgraphs
- Approximating Fault-Tolerant Domination in General Graphs
