A distributed algorithm for minimum distance-k domination in trees

Publikationstyp
Journal Article
Publikationsdatum
2015-03
Sprache
English
Author
Turau, Volker 
Köhler, Sven 
Institut
Telematik E-17 
TORE-URI
http://hdl.handle.net/11420/6393
Enthalten in
Journal of graph algorithms and applications 
Volume
19
Issue
1
Start Page
223
End Page
242
Citation
Journal of Graph Algorithms and Applications 1 (19): 223-242 (2015)
Publisher DOI
10.7155/jgaa.00354
Scopus ID
2-s2.0-84982221149
Publisher
JGAA
While efficient algorithms for finding minimal distance-k dominating sets exist, finding minimum such sets is NP-hard even for bipartite graphs. This paper presents a distributed algorithm to determine a minimum (connected) distance-k dominating set and a maximum distance-2k independent set of a tree T. It terminates in O(height(T)) rounds and uses O(log k) space. To the best of our knowledge this is the first distributed algorithm that computes a minimum (as opposed to a minimal) distanced dominating set for trees. The algorithm can also be applied to general graphs, albeit the distance-k dominating sets are not necessarily minimal.
DDC Class
004: Informatik