An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
From MaRDI portal
Publication:1861569
DOI10.1016/S0166-218X(02)00218-4zbMath1012.68226MaRDI QIDQ1861569
Publication date: 9 March 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
treematchingapproximation algorithmgraphspolynomial algorithmedge-connectivitygraph augmentationspanning subgraph2-edge-connectivity
Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)
Related Items (26)
Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ On the tree augmentation problem ⋮ A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from \(1\) to \(2\) ⋮ A unified approach to approximating partial covering problems ⋮ LP-relaxations for tree augmentation ⋮ Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP ⋮ Approximating (unweighted) tree augmentation via lift-and-project. II ⋮ Path-contractions, edge deletions and connectivity preservation ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality ⋮ 2-node-connectivity network design ⋮ Covering a laminar family by leaf to leaf links ⋮ Kernelization and complexity results for connectivity augmentation problems ⋮ Unnamed Item ⋮ A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius ⋮ Path-Contractions, Edge Deletions and Connectivity Preservation ⋮ Vertex covering by paths on trees with its applications in machine translation ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ 2-node-connectivity network design
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A fast algorithm for cactus representations of minimum cuts
- Fast Algorithms for Finding Nearest Common Ancestors
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Approximation Algorithms for Several Graph Augmentation Problems
- Approximation Algorithms for Graph Augmentation
- Augmentation Problems
- Biconnectivity approximations and graph carvings
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
