Distributed algorithms for edge dominating sets

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

An edge dominating set for a graph G is a set D of edges such that each edge of G is in D or adjacent to at least one edge in D. This work studies deterministic distributed approximation algorithms for finding minimum-size edge dominating sets. The focus is on anonymous port-numbered networks: there are no unique identifiers, but a node of degree d can refer to its neighbours by integers 1, 2, ..., d. The present work shows that in the port-numbering model, edge dominating sets can be approximated as follows: in d-regular graphs, to within 4 − 6/(d + 1) for an odd d and to within 4 − 2/d for an even d; and in graphs with maximum degree Δ, to within 4 − 2/(Δ − 1) for an odd Δ and to within 4 − 2/Δ for an even Δ. These approximation ratios are tight for all values of d and Δ: there are matching lower bounds.
Original languageEnglish
Title of host publicationPODC’10 : Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing
EditorsAndrea Richa, Rachid Guerraoui
Number of pages10
PublisherACM
Publication date2010
Pages365–374
ISBN (Print)978-1-60558-888-9
DOIs
Publication statusPublished - 2010
MoE publication typeA4 Article in conference proceedings
EventACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC) - Zurich, Switzerland
Duration: 25 Jul 201028 Jul 2010
Conference number: 29

Fields of Science

  • 113 Computer and information sciences

Cite this