Pregled bibliografske jedinice broj: 575066
The relation of Connected Set Cover and Group Steiner Tree
The relation of Connected Set Cover and Group Steiner Tree // Theoretical computer science, 438 (2012), 96-101 doi:10.1016/j.tcs.2012.02.035 (međunarodna recenzija, članak, znanstveni)
CROSBI ID: 575066 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
Naslov
The relation of Connected Set Cover and Group Steiner Tree
Autori
Elbassioni, Khaled ; Jelić, Slobodan ; Matijević, Domagoj
Izvornik
Theoretical computer science (0304-3975) 438
(2012);
96-101
Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni
Ključne riječi
Set cover; Connected set cover; Weighted connected set cover; Group Steiner tree; Node weighted group Steiner tree; Covering Steiner tree problem
Sažetak
We report that the Connected Set Cover (CSC) problem is just a special case of the Group Steiner Tree (GST) problem. Based on that we obtain the first algorithm for CSC with polylogarithmic approximation guarantee as well as the first approximation algorithms for the weighted version of the problem and the version with requirements. Moreover, we argue that the inapproximability result of GST will carry on to the weighted version of the CSC problem.
Izvorni jezik
Engleski
Znanstvena područja
Računarstvo
POVEZANOST RADA
Projekti:
235-2352818-1034 - Nelinearni problemi procjene parametara u matematičkim modelima (Jukić, Dragan, MZOS ) ( CroRIS)
Ustanove:
Sveučilište u Osijeku, Odjel za matematiku
Citiraj ovu publikaciju:
Časopis indeksira:
- Current Contents Connect (CCC)
- Web of Science Core Collection (WoSCC)
- Science Citation Index Expanded (SCI-EXP)
- SCI-EXP, SSCI i/ili A&HCI
- Scopus
