Two distributed algorithms for finding the minimum distance-1 and distance-2 dominating sets for a subclass of graphs known as directed split stars are presented in this paper. Finding the minimum dominating set in arbitrary directed graphs is NP-complete, hence, the motivation for identifying a subclass of graphs where determining the minimum dominating sets is tractable. The authors begin with the obligatory definitions of graphs, directed graphs, vertices, edges, and the graph theoretic definitions of a distance-k dominating set and the minimum distance-k dominating set. A minimum distance-k dominating set is the set with the smallest number of vertices that is still a distance-k dominating set. The authors then define a directed split star graph.

Next comes a sequence of proofs about distance-1 and distance-2 domination that rely on the properties of directed split stars. The proofs are dense and can be hard to follow, but they culminate in a proof that shows how to construct the unique minimum distance-1 and distance-2 dominating set of a directed split star graph. The paper then describes two distributed algorithms for building the minimum distance-1 and distance-2 dominating sets. The distributed algorithms assume a computational model of interconnected processors that communicate asynchronously (buffered). The authors also provide correctness proofs for the algorithms.

In trying to understand the usefulness of a directed split star graph, in the introduction, the authors point out that dominating sets can be useful in networks for storing location information of a network node in a particular kind of mobile network. This network, however, is not a directed split star. As an application of directed split stars, the authors point out that directed split star graphs have been proposed as a model of a processor interconnection network and a distributed network. However, I know of no such realization or use of a directed split star in a realized processor interconnection or network. But the lack of a real implementation of a directed split-star network doesn’t take away from the result, only the potential utility of the result.

The paper is well written, but the proofs are dense. The distributed algorithms are alarmingly straightforward. However, it remains to be seen whether a directed split star graph is actually used in any real way.