Better-than-43-approximations for leaf-to-leaf tree and connectivity augmentation

DOI10.1007/S10107-023-02018-3MaRDI QIDQ6608041FDOQ6608041

Author name not available (Why is that?), Rico Zenklusen, Vera Traub

Publication date: 19 September 2024

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationapproximation algorithmsconnectivity augmentationtree augmentation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Geometric algorithms and combinatorial optimization.
• Title not available (Why is that?)
• A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Rooted \(k\)-connections in digraphs
• A factor 2 approximation algorithm for the generalized Steiner network problem
• On the integrality ratio for tree augmentation
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• Title not available (Why is that?)
• Covering a laminar family by leaf to leaf links
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Approximation Algorithms for Graph Augmentation
• Approximation algorithms for connectivity augmentation problems
• Approximation Algorithms for Several Graph Augmentation Problems
• Improved approximation for tree augmentation: saving by rewiring
• LP-relaxations for tree augmentation
• Approximating (unweighted) tree augmentation via lift-and-project. II
• On the tree augmentation problem
• Title not available (Why is that?)
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• Parameterized Algorithms to Preserve Connectivity

Cited In (2)

• Approximation algorithms for node and element connectivity augmentation problems
• Improved first player strategy for the zero-sum sequential uncrossing game

This page was built for publication: Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation

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