Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
From MaRDI portal
Publication:1799605
DOI10.1016/j.ipl.2018.08.003zbMath1483.68260arXiv1703.04230OpenAlexW2595035909WikidataQ129370187 ScholiaQ129370187MaRDI QIDQ1799605
Publication date: 19 October 2018
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1703.04230
Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Connectivity (05C40)
Related Items (3)
Approximating \(k\)-connected \(m\)-dominating sets ⋮ Construction of minimum edge-fault tolerant connected dominating set in a general graph ⋮ Approximating k-Connected m-Dominating Sets
Cites Work
- Unnamed Item
- Unnamed Item
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- Approximating node connectivity problems via set covers
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
- Approximating subset \(k\)-connectivity problems
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
- Approximating minimum-cost connectivity problems via uncrossable bifamilies
- Tight bounds for the vertices of degree k in minimally k‐connected graphs
- A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
- Approximating Fault-Tolerant Domination in General Graphs
- Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
This page was built for publication: Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
