Approximation Algorithms for Graph Augmentation
From MaRDI portal
Publication:4033765
DOI10.1006/jagm.1993.1010zbMath0764.68120OpenAlexW2002452451MaRDI QIDQ4033765
Ramakrishna Thurimella, Samir Khuller
Publication date: 16 May 1993
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1993.1010
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Related Items (27)
Better algorithms for minimum weight vertex-connectivity problems ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ On the tree augmentation problem ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ Correlation clustering and two-edge-connected augmentation for planar graphs ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ A genetic approach for the 2‐edge‐connected minimum branch vertices problem ⋮ LP-relaxations for tree augmentation ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ An approximation algorithm for minimum-cost vertex-connectivity problems ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality ⋮ 2-node-connectivity network design ⋮ A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs ⋮ A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation ⋮ Kernelization and complexity results for connectivity augmentation problems ⋮ A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation ⋮ Unnamed Item ⋮ Path hitting in acyclic graphs ⋮ Faster approximation algorithms for weighted triconnectivity augmentation problems ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ On small-depth tree augmentations ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem ⋮ An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree ⋮ Evolutionary local search for the edge-biconnectivity augmentation problem ⋮ 2-node-connectivity network design
This page was built for publication: Approximation Algorithms for Graph Augmentation
