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

DOI10.1016/J.IPL.2021.106175MaRDI QIDQ2234806zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsdominating set2-edge-connected set

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithms for connected dominating sets
• Approximation algorithms for connected dominating sets
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• On approximating (connected) 2-edge dominating set by a tree
• On approximating (connected) 2-edge dominating set by a tree

Cites work

• scientific article; zbMATH DE number 6297807 (Why is no real title available?)
• 2-node-connectivity network design
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Approximation Algorithms for Directed Steiner Problems
• Approximation algorithms for connected dominating sets
• Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
• Parameterized algorithms to preserve connectivity
• Polylogarithmic inapproximability

Cited in

(9)

• Approximating \(k\)-connected \(m\)-dominating sets
• 2-node-connectivity network design
• On approximating (connected) 2-edge dominating set by a tree
• On approximating (connected) 2-edge dominating set by a tree
• New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
• A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• A novel local search approach with connected dominating degree-based incremental neighborhood evaluation for the minimum 2-connected dominating set problem
• Construction of minimum edge-fault tolerant connected dominating set in a general graph
• 2-node-connectivity network design

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2234806)