A New Optimality Measure for Distance Dominating Sets
Narges Simjour · UWSpace (University of Waterloo) · 2006
I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii We study the problem of finding the smallest power of an input graph that has k disjoint dominating sets, where the ith power of an input graph G is constructed by adding edges between pairs of vertices in G at distance i or less, and a subset of vertices in a graph G is a dominating set if and only if every vertex in G is adjacent to a vertex in this subset. The problem is a different view of the d-domatic number problem in which the goal is to find the maximum number of disjoint dominating sets in the dth power of the input graph. This problem is motivated by applications in multi-facility location and dis-tributed networks. In the facility location framework, for instance, there are k types of services that all clients in different regions of a city should receive. A