2024/07/15 by Ali Çivril, Çivril, Ali · 1 voice
Materials Science · Mathematics · Computer Science · #Graphene research and applications #Graph theory and applications #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2407.10526
We provide algorithms for the minimum 2-edge-connected spanning subgraph problem and the minimum 2-vertex-connected spanning subgraph problem with approximation ratio (9)/(7). This improves upon a recent algorithm with ratio slightly smaller than (4)/(3) for 2-edge-connectivity, and another one with ratio (4)/(3) for 2-vertex-connectivity.