Download

Open access
Author
Kuhn, Fabian
Wattenhofer, Roger
Date
2003Type
- Report
ETH Bibliography
yes
Altmetrics
Download
Abstract
Finding a small dominating set is one of the most fundamental problems of traditional graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary parameter $k$, our algorithm computes a dominating set of expected size $\bigO{k\Delta^{2/k}\log\Delta|\dsopt|}$ in $\bigO{k^2}$ rounds where each node has to send $\bigO{k^2\Delta}$ messages of size $\bigO{\log\Delta}$. This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds Show more
Permanent link
https://doi.org/10.3929/ethz-a-006665828Publication status
publishedExternal links
Search via SFX
Journal / series
Technical reportVolume
Publisher
ETH, Swiss Institute of Technology, Department of Computer Science, Distributed Computing GroupSubject
LP-Relaxation; Approximation algorithms; Distributed algorithms; Dominating setOrganisational unit
02150 - Dep. Informatik / Dep. of Computer Science
Notes
Technical reports D-Infk. See also http://e-citations.ethbib.ethz.ch/view/pub:53607.More
Show all metadata
ETH Bibliography
yes
Altmetrics