Please use this identifier to cite or link to this item: doi:10.22028/D291-38305
Title: Distributed distance-r covering problems on sparse high-girth graphs
Author(s): Amiri, Saeed Akhoondian
Wiederhake, Ben
Language: English
Title: Theoretical Computer Science
Volume: 906
Pages: 18-31
Publisher/Platform: Elsevier
Year of Publication: 2022
Free key words: Sparse graphs
Dominating set
Vertex cover
Upper bound
Lower bound
DDC notations: 004 Computer science, internet
Publikation type: Journal Article
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 of the first publication: 10.1016/j.tcs.2022.01.001
URL of the first publication:
Link to this record: urn:nbn:de:bsz:291--ds-383055
ISSN: 0304-3975
Date of registration: 30-Nov-2022
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Professorship: MI - Keiner Professur zugeordnet
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
1-s2.0-S0304397522000081-main.pdf464,95 kBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons