Title: 圖的無k點子樹支配問題
T_k-free Domination in Graphs
Authors: 曾湄菁
Mei-Jing Tzeng
Gerard J. Chang
Keywords: 支配;無k點子樹;樹;塊圖;domination;tree-free;tree;block graphs
Issue Date: 2000
Abstract: 在一個圖G中, 每一個點都可以支配(dominate)它自己以及和它相鄰的點。對一個固定的正整數k (k>=2)而言,無k點子樹支配問題就是去找出最小的點集合,使得圖G中的每個點都可以被這個點集合支配,而這個點集合中沒有 k 點子樹圖﹝不見得一定得是延伸(induced subgraph)圖﹞存在,也就是說,每個部份(component)的大小要小於k。當k=2時,討論無k點子樹問題等於討論一般圖的獨立支配數 r_i(G),當k>=(n+1)/2時,討論無k點子樹支配問題等於討論一般圖的支配數r(G)。在這篇論文中,我們從演算法的角度來看無k點子樹支配問題,我們使用動態規劃(dynamic programming method)設計有效率的演算法,去解決在樹(tree)和塊圖(block graphs)上的無k點子樹分配問題。
The Tk-free domination number r(G;-T_k), k>=2, of a graph G is the minimum cardinality of a dominating set D such that the subgraph <D> induced by D contains no tree of k vertices as a (not necessarily induced) subgraph; or equivalently, each component of <D> has less than k vertices. When k=2, the T_k-free domination number is the independent domination number; when k>=(n+1)/2 , the T_k-free domination is the usual domination. In this thesis, we study T_k-free domination from an algorithmic point of view. In particular, we present efficient algorithms for the problem on trees and block graphs by the dynamic programming method.
Appears in Collections:Thesis