Covering a laminar family by leaf to leaf links

DOI10.1016/J.DAM.2010.04.002MaRDI QIDQ987693zbMATH OpenOpenAlexFDO

Authors Yael Maduel, Zeev Nutov

Publication date 13 August 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.04.002

zbMATH Keywords

approximation algorithmbest approximation ratioedge-connectivityedge-coverlaminar family

Mathematics Subject Classification ID

Trees (05C05) Approximation algorithms (68W25)

Recommendations

• LP-relaxations for tree augmentation
• Improved approximation for tree augmentation: saving by rewiring
• A (1 + 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• Fast distributed approximation for TAP and 2-edge-connectivity

Cites work

• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A factor 2 approximation algorithm for the generalized Steiner network problem
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• scientific article; zbMATH DE number 1833404 (Why is no real title available?)
• scientific article; zbMATH DE number 1405806 (Why is no real title available?)
• On the integrality ratio for tree augmentation
• On the relationship between the biconnectivity augmentation and traveling salesman problems

Cited in

(15)

• LP-relaxations for tree augmentation
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• Fast distributed approximation for TAP and 2-edge-connectivity
• Approximation algorithms for connectivity augmentation problems
• 2-node-connectivity network design
• On the tree augmentation problem
• A (1 + 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• Fast distributed approximation for TAP and 2-edge-connectivity
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• LP-relaxations for tree augmentation
• scientific article; zbMATH DE number 7205039 (Why is no real title available?)
• 2-node-connectivity network design
• Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
• 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: Covering a laminar family by leaf to leaf links

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