A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph

DOI10.1006/jagm.1999.1006zbMath0951.68111OpenAlexW1984289304MaRDI QIDQ4719338

Domenico Parente, Yefim Dinitz, Zeev Nutov, Vincenzo Auletta

Publication date: 18 December 2000

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1999.1006

zbMATH Keywords

\(k\)-vertex connected graphs

Mathematics Subject Classification ID

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

Related Items (20)

Improved approximation algorithms for single-tiered relay placement ⋮ Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Approximating subset \(k\)-connectivity problems ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach ⋮ On extremal \(k\)-outconnected graphs ⋮ 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 ⋮ 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 ⋮ Approximating survivable networks with \(\beta \)-metric costs ⋮ Power assignment for \(k\)-connectivity in wireless ad hoc networks ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems ⋮ Approximating minimum-power edge-covers and 2,3-connectivity ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ Relay placement for two-connectivity

This page was built for publication: A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph