Improved Approximation Algorithms for Uniform Connectivity Problems
From MaRDI portal
Publication:4895812
DOI10.1006/jagm.1996.0052zbMath0857.68052OpenAlexW2078501279MaRDI QIDQ4895812
Samir Khuller, Balaji Raghavachari
Publication date: 16 October 1996
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1996.0052
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items
Improved approximation algorithms for single-tiered relay placement ⋮ Performance guarantees for the TSP with a parameterized triangle inequality ⋮ Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Approximating subset \(k\)-connectivity problems ⋮ Approximating Steiner Trees and Forests with Minimum Number of Steiner Points ⋮ Power optimization in ad hoc wireless network topology control with biconnectivity requirements ⋮ Power optimization for connectivity problems ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ On a partition LP relaxation for min-cost 2-node connected spanning subgraphs ⋮ Relay placement for fault tolerance in wireless networks in higher dimensions ⋮ Degree constrained node-connectivity problems ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ An approximation algorithm for minimum-cost vertex-connectivity problems ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems ⋮ Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems ⋮ Approximating the smallest k -edge connected spanning subgraph by LP-rounding ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Faster approximation algorithms for weighted triconnectivity augmentation problems ⋮ Relay placement for two-connectivity ⋮ Unnamed Item
This page was built for publication: Improved Approximation Algorithms for Uniform Connectivity Problems
