Jukka Suomela

Distributed algorithms for edge dominating sets

PODC 2010 · 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Zurich, Switzerland, July 2010 · doi:10.1145/1835698.1835783

author’s version publisher’s version

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.

Errata

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.

Publication

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

ISBN 978-1-60558-888-9

Links

© ACM 2010 — This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proc. 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. http://doi.acm.org/10.1145/1835698.1835783

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.