Universität zu Köln

Amiri, Saeed Akhoondian and Wiederhake, Ben (2022). Distributed distance-r covering problems on sparse high-girth graphs. Theor. Comput. Sci., 906. S. 18 - 32. AMSTERDAM: ELSEVIER. ISSN 1879-2294

Full text not available from this repository.

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. (C) 2022 The Authors. Published by Elsevier B.V.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Amiri, Saeed Akhoondian UNSPECIFIED UNSPECIFIED UNSPECIFIED Wiederhake, Ben UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-672402
DOI:	10.1016/j.tcs.2022.01.001
Journal or Publication Title:	Theor. Comput. Sci.
Volume:	906
Page Range:	S. 18 - 32
Date:	2022
Publisher:	ELSEVIER
Place of Publication:	AMSTERDAM
ISSN:	1879-2294
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language Computer Science, Theory & Methods Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/67240