Approximation Algorithms for Graph Augmentation
From MaRDI portal
Publication:4033765
DOI10.1006/JAGM.1993.1010zbMATH Open0764.68120OpenAlexW2002452451MaRDI QIDQ4033765FDOQ4033765
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
Recommendations
- Approximation algorithms for graph augmentation
- A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- scientific article; zbMATH DE number 1760036
- NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems
- scientific article; zbMATH DE number 1833404
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Cited In (44)
- Fast distributed approximation for TAP and 2-edge-connectivity
- Algorithms and Computation
- Title not available (Why is that?)
- Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
- Title not available (Why is that?)
- Evolutionary local search for the edge-biconnectivity augmentation problem
- An approximation algorithm for minimum-cost vertex-connectivity problems
- On the tree augmentation problem
- A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation
- Approximation algorithms for vertex-connectivity augmentation on the cycle
- Path hitting in acyclic graphs
- 2-node-connectivity network design
- Faster approximation algorithms for weighted triconnectivity augmentation problems
- Node connectivity augmentation via iterative randomized rounding
- On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
- Kernelization and complexity results for connectivity augmentation problems
- Fast Distributed Approximation for TAP and 2-Edge-Connectivity
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- Correlation clustering and two-edge-connected augmentation for planar graphs
- Polynomial time algorithms for 2-edge-connectivity augmentation problems
- On finding augmenting graphs
- Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
- A genetic approach for the 2‐edge‐connected minimum branch vertices problem
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for node and element connectivity augmentation problems
- A simple LP-based approximation algorithm for the matching augmentation problem
- Title not available (Why is that?)
- Approximation algorithms for graph augmentation
- Augmenting graphs to minimize the diameter
- A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
- Better algorithms for minimum weight vertex-connectivity problems
- Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length
- LP-relaxations for tree augmentation
- Title not available (Why is that?)
- 2-node-connectivity network design
- Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
- On the cycle augmentation problem: hardness and approximation algorithms
- On small-depth tree augmentations
- A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation
This page was built for publication: Approximation Algorithms for Graph Augmentation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4033765)
