A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
Yazarlar (1)
Prof. Dr. Ali ÇİVRİL Beykoz Üniversitesi, Türkiye
| Makale Türü | Özgün Makale (SSCI, AHCI, SCI, SCI-Exp dergilerinde yayınlanan tam makale) | ||
| Dergi Adı | Theoretical Computer Science (Q3) | ||
| Dergi ISSN | 0304-3975 Wos Dergi Scopus Dergi | ||
| Dergi Tarandığı Indeksler | SSCI | ||
| Makale Dili | İngilizce | Basım Tarihi | 01-2023 |
| Cilt / Sayı / Sayfa | 943 / 1 / 121–130 | DOI | 10.1016/j.tcs.2022.12.013 |
| Makale Linki | https://www.sciencedirect.com/science/article/pii/S0304397522007368 | ||
| UAK Araştırma Alanları |
Algoritmalar ve Hesaplama Kuramı
|
||
| Özet |
| We present a new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem. Its approximation ratio is [Formula presented], which matches the current best ratio. The approximation ratio of the algorithm is [Formula presented] on subcubic graphs, which is an improvement upon the previous best ratio of [Formula presented]. The algorithm is a novel extension of the primal-dual schema, which consists of two distinct phases. Both the algorithm and the analysis are much simpler than those of the previous approaches. |
| Anahtar Kelimeler |
| Approximation algorithms | Combinatorial optimization | Minimum 2-edge-connected spanning subgraph problem |
Science Direct
A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
BM Sürdürülebilir Kalkınma Amaçları
| Atıf Sayıları | |
| Scopus | 2 |