A better-than-2 approximation for weighted tree augmentation

DOI10.1109/FOCS52979.2021.00010MaRDI QIDQ6943542zbMATH OpenFDO

Authors Vera Traub, Rico Zenklusen

Publication date 13 August 2025

Full work available at URL https://doi.org/10.1109/FOCS52979.2021.00010

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Proceedings, conferences, collections, etc. pertaining to information and communication theory (94-06)

Cited in

(10)

• Streaming algorithms for connectivity augmentation
• On the bidirected cut relaxation for Steiner forest
• A 4/3 approximation for 2-vertex-connectivity
• An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover
• Hypergraph connectivity augmentation in strongly polynomial time
• Approximation algorithms for Steiner connectivity augmentation
• Survivable network design with group-to-group requirement
• Protecting the connectivity of a graph under non-uniform edge failures
• Protecting the connectivity of a graph under nonuniform edge failures
• Streaming algorithms for network design

This page was built for publication: A better-than-2 approximation for weighted tree augmentation

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