A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs

DOI10.1006/jagm.1999.1007zbMath0951.68112OpenAlexW2047948011MaRDI QIDQ4719339

Yefim Dinitz, Zeev Nutov

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

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

This page was built for publication: A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs