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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Variations of Dominating Set Problem

  • Liying Kang,
  • Shou-Jun Xu

摘要

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.