2-node-connectivity network design

DOI10.1007/978-3-030-80879-2_15MaRDI QIDQ2117701OpenAlexFDO

Authors Zeev Nutov

Publication date 22 March 2022

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

zbMATH Keywords

approximation algorithmdominating set2-connectivityblock-tree augmentationsymmetric crossing family

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 1263227 (Why is no real title available?)
• scientific article; zbMATH DE number 6850362 (Why is no real title available?)
• scientific article; zbMATH DE number 1405806 (Why is no real title available?)
• scientific article; zbMATH DE number 7205039 (Why is no real title available?)
• scientific article; zbMATH DE number 6297807 (Why is no real title available?)
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• A polylogarithmic approximation algorithm for 2-edge-connected dominating set
• A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Approximation Algorithms for Graph Augmentation
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximation algorithms for connected dominating sets
• Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
• Covering a laminar family by leaf to leaf links
• Coverings and structure of crossing families
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Improved approximation for tree augmentation: saving by rewiring
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Lower-Stretch Spanning Trees
• On the integrality ratio for tree augmentation
• Parameterized algorithms to preserve connectivity
• Pruning 2-connected graphs

Cited in

(11)

• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
• On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
• Approximating \(k\)-connected \(m\)-dominating sets
• scientific article; zbMATH DE number 4043770 (Why is no real title available?)
• Node connectivity augmentation via iterative randomized rounding
• \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
• A polylogarithmic approximation algorithm for 2-edge-connected dominating set
• Approximation algorithms for node and element connectivity augmentation problems
• 2-node-connectivity network design
• Approximation algorithms for vertex-connectivity augmentation on the cycle

This page was built for publication: 2-node-connectivity network design

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