A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
From MaRDI portal
Publication:4719339
DOI10.1006/jagm.1999.1007zbMath0951.68112OpenAlexW2047948011MaRDI QIDQ4719339
Publication date: 7 January 2001
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/86aa1e76e9d621deddb355a48402f0233c095ea8
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Improved approximation algorithms for minimum cost node-connectivity augmentation problems, Approximating subset \(k\)-connectivity problems, An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach, Relay placement for fault tolerance in wireless networks in higher dimensions, A \(4+\epsilon\) approximation for \(k\)-connected subgraphs, Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems, On minimum power connectivity problems, ON THE VERTEX-CONNECTIVITY PROBLEM FOR GRAPHS WITH SHARPENED TRIANGLE INEQUALITY, Power assignment for \(k\)-connectivity in wireless ad hoc networks, On \(k\)-connectivity problems with sharpened triangle inequality, Approximating minimum-power edge-covers and 2,3-connectivity