摘要
令G = (V,E)為一有頂點集 V 與邊集 E 的圖，而 T 為 V 之一個子 集，一 G 對於 T 的端點路徑覆蓋PC 是 G 一兩兩頂點互斥路徑的集，此集合覆蓋G 之頂點，使得 T 所有的頂點都是PC中路徑的端點，端點路徑覆蓋問題即是要尋找G 之一具有對於T 最少元素數(minimum cardinality)的端點路徑覆蓋，路徑覆蓋問題乃是端點路徑覆蓋問題在T 為空集合時的一個特殊狀況，而該終端的路徑覆蓋問題是要找到一個終端路徑覆蓋 G 的最小基數。而如果 T 是空的，所描述的問題相吻合於傳統路徑覆蓋問題，在本論文中，我們首先利用一些圖形類別來說明路徑覆蓋問題可以在線性時間上解決路徑覆蓋上的問題，區塊圖則是其中之一，因此，終端路徑覆蓋的問題，可以簡化成路徑覆蓋問題;另一方面，我們給予樹形分解型態(tree-like decomposition structure)，來表示區塊圖(block graph)，要顯示所提出樹形結構的效率，我們用它來設計一個動態規化線性演算法以直接解決終端路徑覆蓋問題，而不使用簡化的技巧，本文亦要證明樹狀圖上的端點路徑覆蓋問題能於線性時間解之。
並列摘要
Let G = (V,E) be a graph with vertex set V and edge set E and let T be a subset of V. A terminal path cover PC of G with respect to T is a set of pairwise vertex-disjoint paths of G which cover the vertices of G such that all vertices in T are end vertices of paths in PC. The terminal path cover problem is to find a terminal path cover of G of minimum cardinality with respect to T . The path cover problem is a special case of the terminal path cover problem with T being empty. Note that, if T is empty, the stated problem coincides with the classical path cover problem. We first show that for some graph classes, the terminal path cover problem can be reduced to the path cover problem in linear time. The class of block graphs is one of the stated graph classes and, hence, the terminal path cover problem in it can be reduced to the path cover problem. On the other hand,we give a tree-like decomposition structure to represent a block graph. To show the efficiency of proposed tree-like structure, we use it to design a dynamic programming linear-time algorithm for directly solving the terminal path cover problem in block graphs by not using the stated reduction. We also show that the terminal path cover problem on trees can be solved in linear time.
參考文獻
[19] R.W. Hung, A linear-time algorithm for the terminal path cover problem in
[23] R.W. Hung and C.A. Fang, A linear-time algorithm for the terminal path
[24] R.W. Hung, A linear-time algorithm for the terminal path cover problem in
numbers of trees, Discrete Math. 155 (2007) 1700-1707.
problem on interval graphs, Inform. Process. Lett. 35 (1990) 149-153.