A polylogarithmic approximation algorithm for 2-edge-connected dominating set

DOI10.1016/j.ipl.2021.106175zbMath1476.05150OpenAlexW3188033804MaRDI QIDQ2234806

Amir Belgi, Zeev Nutov

Publication date: 19 October 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2021.106175

zbMATH Keywords

dominating setapproximation algorithms2-edge-connected set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (4)

Approximating \(k\)-connected \(m\)-dominating sets ⋮ Construction of minimum edge-fault tolerant connected dominating set in a general graph ⋮ 2-node-connectivity network design ⋮ 2-node-connectivity network design

Cites Work

• Approximation algorithms for connected dominating sets
• Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
• 2-node-connectivity network design
• Polylogarithmic inapproximability
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Approximation Algorithms for Directed Steiner Problems
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Parameterized Algorithms to Preserve Connectivity
• Unnamed Item

This page was built for publication: A polylogarithmic approximation algorithm for 2-edge-connected dominating set