仙人掌圖上的成對支配點問題

Abstract

本論文提出一個演算法來解決仙人掌圖上的成對支配點問題。試想一個由點與線構成的圖,支配集是圖上的點構成的點集合,而圖上每個不在支配集裡的點都會至少與一個在支配集裡的點相鄰,如此就構成了支配集。而對於一個圖上的成對支配點集來說,既滿足支配集的定義又滿足支配集裡點形成的誘導子圖上,點兩兩成對。在一個圖上無數成對支配集中,如何找到一個成對支配集且此集合點的數量為無數成對支配點中最少的,就是成對支配點問題。此外,只要一張連通圖是由許多環或邊組成,且任意兩環只會有一個共同交點,就稱之為仙人掌圖。仙人掌圖常用於無線網路的模型中,而成對支配集可以用來解決資源配置以及備份的問題。 在此篇論文中,給予一個仙人掌圖G,令n為點之數量,我們提出了一個可在O(n)時間內找出在G上之最小成對支配點集合的演算法。

A set S⊆V is a dominating set of a graphG=(V,E) if every vertex not in S is adjacent to a vertex in S. A dominating set S of a graph G is called a paired-dominating set if the induced subgraph G[S] contains a perfect matching. The paired-domination problem is to find the paired-dominating set of a graph with minimum size. A block in a graph G is a maximal connected subgraph of G without cut vertices. A cactus graph is a connected graph in which each block is either an edge or a cycle. Any two simple cycles have at most one vertex in common. Cactus graph usually used to model wireless network in some situation, and paired-domination problem can be used to solve problems of resource allocation and backup. In this thesis, we provide a greedy method algorithm with O(n)-time for the paired-domination problem on cactus graphs.