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.
End of Section 4.1: “(pd,l) ↔ (bl,l,d) ∀l = 1,2,...,d” should be “(pd,l) ↔ (bl,l,d) ∀l = 1,2,...,d−1”. Thanks to Behnam Tavakoli for noticing this.
Andrea Richa and Rachid Guerraoui (Eds.): PODC’10, Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing, July 25–28, 2010, Zurich, Switzerland, pages 365–374, ACM Press, New York, 2010