Approximation of Steiner forest via the bidirected cut relaxation
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ı | Journal of Combinatorial Optimization (Q4) | ||
| Dergi ISSN | 1382-6905 Wos Dergi Scopus Dergi | ||
| Dergi Tarandığı Indeksler | SCI | ||
| Makale Dili | İngilizce | Basım Tarihi | 11-2019 |
| Cilt / Sayı / Sayfa | 38 / 4 / 1196–1212 | DOI | 10.1007/s10878-019-00444-8 |
| Makale Linki | https://arxiv.org/pdf/1911.07234 | ||
| UAK Araştırma Alanları |
Algoritmalar ve Hesaplama Kuramı
|
||
| Özet |
| The classical algorithm of Agrawal, Klein and Ravi [SIAM J. Comput., 24 (1995), pp. 440-456], stated in the setting of the primal-dual schema by Goemans and Williamson [SIAM J. Comput., 24 (1995), pp. 296-317] uses the undirected cut relaxation for the Steiner forest problem. Its approximation ratio is $2-\frac{1}{k}$, where $k$ is the number of te... |
| Anahtar Kelimeler |
| Approximation algorithms | Bidirected cut relaxation | Combinatorial optimization | Primal-dual schema | Steiner forest |
BM Sürdürülebilir Kalkınma Amaçları
| Atıf Sayıları | |
| Web of Science | 2 |
| Scopus | 2 |
| Google Scholar | 4 |