Variations of Dominating Set Problem
摘要
Domination and its variations in graphs have been extensively studied. The basic problem is as follows: Given an undirected graph G = (V, E), determine a minimum-size vertex set S ⊆ V such that each vertex v is contained in S or v is a neighbor of at least one vertex in S. In this chapter, we study three variants of domination, power domination, paired-domination, and total domination, which were widely studied in recent years. We give a review of these variants of domination from complexity, approximation algorithm, polynomial algorithm, and bound.