arXiv Open Access 2023

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph

Ali Çivril

Lihat Sumber

Abstrak

We provide algorithms for the minimum 2-edge-connected spanning subgraph problem and the minimum 2-vertex-connected spanning subgraph problem with approximation ratio both $\frac{4}{3}$. Using a common theme, the algorithms and their analyses are very similar.

Topik & Kata Kunci

cs.DS

Penulis (1)

Ali Çivril

Format Sitasi

APA MLA BibTeX

Çivril, A. (2023). A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph. https://arxiv.org/abs/2305.05398

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2023
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓