Domination based algorithm tok-center problem
A. Anto Kinsley, S. Somasundaram · Journal of Discrete Mathematical Sciences and Cryptography · 2006
In this paper we consider a k-center location problem, which is based on the dominating set problem. The computation of the minimum dominating sets of a graph is used as a basic step for the determination of k-centers of the graph. We first study reachable sets [2], [5], link vectors [2] of the vertices and then introduce two binary operations ⋁ and ⋀ for finding the dominating sets. These are used as tools for designing an algorithm to find the k-centers. We construct G λ-graphs [2], [4] and then we investigate their dominating sets. Some required results for developing algorithms are also proved. Using these concepts we present an algorithm to find all k-centers of a graph. We show that the domination based k-center problem is NP complete.