Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-38305
Titel: | Distributed distance-r covering problems on sparse high-girth graphs |
VerfasserIn: | Amiri, Saeed Akhoondian Wiederhake, Ben |
Sprache: | Englisch |
Titel: | Theoretical Computer Science |
Bandnummer: | 906 |
Seiten: | 18-31 |
Verlag/Plattform: | Elsevier |
Erscheinungsjahr: | 2022 |
Freie Schlagwörter: | Sparse graphs Dominating set Vertex cover Upper bound Lower bound |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Journalartikel / Zeitschriftenartikel |
Abstract: | We prove that the distance-r dominating set, distance-r connected dominating set, distance-r vertex cover, and distance-r connected vertex cover problems admit constant factor approximations in the CONGEST model of distributed computing in a constant number of rounds on classes of sparse high-girth graphs. In this paper, sparse means bounded expansion, and high-girth means girth at least 4r + 2. Our algorithm is quite simple; however, the proof of its approximation guarantee is non-trivial. To complement the algorithmic results, we show tightness of our approximation by providing a loosely matching lower bound on rings. Our result is the first to show the existence of constant-factor approximations in a constant number of rounds in non-trivial classes of graphs for distance-r covering problems. |
DOI der Erstveröffentlichung: | 10.1016/j.tcs.2022.01.001 |
URL der Erstveröffentlichung: | http://dx.doi.org/10.1016/j.tcs.2022.01.001 |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291--ds-383055 hdl:20.500.11880/34562 http://dx.doi.org/10.22028/D291-38305 |
ISSN: | 0304-3975 |
Datum des Eintrags: | 30-Nov-2022 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Professur: | MI - Keiner Professur zugeordnet |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
1-s2.0-S0304397522000081-main.pdf | 464,95 kB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons