圖的k多重支配問題

Abstract

在一個圖G中, 每一個點都可以支配(dominate)它自己以及和它相鄰的點. 對一個固定的正整數k而言, k多重支配問題就是去找出最小的點集合, 使得圖G中的每個點都可以被這個點集合中至少k點支配. 這篇論文主要是從演算法的角度來研究這個問題. 我們的結果包括下面幾項; 首先, 我們提供了兩個線性時間的演算法, 分別解決了樹(trees)以及強弦圖(strongly chordal graphs)上的k多重支配問題; 此外, 我們也證明了在分裂圖(split graphs)(弦圖(chordal graphs)的子類)以及二分圖(bipartite graphs)中, k多重支配問題是NP完備的

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current thesis studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give linear-time algorithms for the k-tuple domination problem in trees and strongly chordal graphs by employing a labeling method. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and bipartite graphs.