Approximating \(k\)-connected \(m\)-dominating sets

DOI10.1007/s00453-022-00935-xzbMath1500.68007arXiv1902.03548OpenAlexW4213218991MaRDI QIDQ2144267

Zeev Nutov

Publication date: 1 June 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1902.03548

zbMATH Keywords

approximation algorithms\(k\)-connected graph\(m\)-dominating setsubset \(k\)-connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (1)

\(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms

Cites Work

• 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
• Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
• Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
• On the optimal vertex-connectivity augmentation
• 2-node-connectivity network design
• A polylogarithmic approximation algorithm for 2-edge-connected dominating set
• 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 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
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• Approximating Fault-Tolerant Domination in General Graphs
• Approximating k-node Connected Subgraphs via Critical Graphs

This page was built for publication: Approximating \(k\)-connected \(m\)-dominating sets