Approximating k-Connected m-Dominating Sets
From MaRDI portal
Publication:5874545
DOI10.4230/LIPICS.ESA.2020.73OpenAlexW3081528035MaRDI QIDQ5874545FDOQ5874545
Authors: Zeev Nutov 
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
Cites Work
- Unit disk graphs
- Title not available (Why is that?)
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- Approximation algorithms for connected dominating sets
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
- On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
- New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
- Simple heuristics for unit disk graphs
- Approximating node connectivity problems via set covers
- Approximating subset \(k\)-connectivity problems
- On the optimal vertex-connectivity augmentation
- Node-weighted Steiner tree approximation in unit disk graphs
- Independence free graphs and vertex connectivity augmentation
- Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
- Approximating minimum-cost connectivity problems via uncrossable bifamilies
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
- Approximating source location and star survivable network problems
- Approximating Fault-Tolerant Domination in General Graphs
- Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
- A 4 + ε approximation for k-connected subgraphs
- Erratum
- Spider Covers for Prize-Collecting Network Activation Problem
Cited In (10)
- Approximating \(k\)-connected \(m\)-dominating sets
- Probabilistic analysis of upper bounds for 2-connected distance \(k\)-dominating sets in graphs
- 2-node-connectivity network design
- On approximating (connected) 2-edge dominating set by a tree
- Title not available (Why is that?)
- Approximation algorithms for connected dominating sets
- Title not available (Why is that?)
- Approximation algorithm for (connected) Italian dominating function
- Approximating \(k\)-generalized connectivity via collapsing HSTs
- Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges
This page was built for publication: Approximating k-Connected m-Dominating Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874545)
