article · 2013

Distributed minimum dominating set . . .

Christoph Lenzen, Yvonne-Anne Pignolet, Roger Wattenhofer

Cited by 0Abstract and details only

Abstract

A dominating set is a subset of the nodes of a graph such that all nodes are in the set or adjacent to a node in the set. A minimum dominating set approximation is a dominating set that is not much larger than a dominating set with the fewest possible number of nodes. This article summarizes the state-of-the-art with respect to finding minimum dominating set approximations in distributed systems, where each node locally executes a protocol on its own, communicating with its neighbors in order to achieve a solution with good global properties. Moreover, we present a number of recent results for specific families of graphs in detail. A unit disk graph is given by an embedding of the nodes in the Euclidean plane, where two nodes are joined by an edge exactly if they are in distance at most one. For this family of graphs, we prove an asymptotically tight lower bound on the trade-off between time complexity and approximation ratio of deterministic algorithms. Next, we consider graphs of small arboricity, whose edge sets can be decomposed into a small number of forests. We give two

Cite this paper

APA 7

Lenzen, C., Pignolet, Y.-A., & Wattenhofer, R. (2013). Distributed minimum dominating set . . .

MLA 9

Lenzen, Christoph, et al. “Distributed minimum dominating set . . .” 2013.

Chicago

Lenzen, Christoph, Yvonne-Anne Pignolet, and Roger Wattenhofer. 2013. “Distributed minimum dominating set . . .”

Harvard

Lenzen, C., Pignolet, Y.-A. and Wattenhofer, R. (2013) ‘Distributed minimum dominating set . . ’.

BibTeX

@article{lenzen2013distributed,
  title = {{Distributed minimum dominating set . . .}},
  author = {Lenzen, Christoph and Pignolet, Yvonne-Anne and Wattenhofer, Roger},
  year = {2013}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.