臺灣博碩士論文加值系統

令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.

中文摘要 ................................................................................................................. i
Abstract ................................................................................................................... ii
誌謝 .......................................................................................................................iii
List of Figures ......................................................................................................... v
List of Tables ......................................................................................................... vi
Chapter 1. Introduction ........................................................................................... 1
1.1. Framework- motivation ............................................................................... 1
1.2. Contribution ................................................................................................. 3
1.3. Related works ............................................................................................... 4
Chapter 2: A Survey on Trees and Block Graphs .................................................. 5
Chapter 3: Reducing the Terminal Path Cover Problem to the Path Cover
Problem ............................................................................................... 17
Chapter 4: A Linear-Time Algorithm for the Terminal Path Cover Problem in
Trees ................................................................................................... 21
Chapter 5: A Linear-Time Algorithm for the Terminal Path Cover Problem in
Block Graphs ...................................................................................... 30
5.1. The background results .............................................................................. 30
5.2. The block tree ............................................................................................. 31
5.3. Computing the terminal path cover numbers for block nodes ................... 34
5.4. Computing the related terminal path cover numbers for cut nodes ........... 38
5.5 The Algorithm ............................................................................................. 45
Chapter 6: Conclusions and Future Research ....................................................... 48
Reference .............................................................................................................. 49

List of Figures
Fig. 1: The complexity status (NP-complete, Polynomial) of the path cover
problem for some graph subclasses of perfect graphs, where A ® B
indicates class A contains class B. ........................................................... 2
Fig. 2: (a) A tree, and (b) a rooted tree of (a) with root υ2 , where the terminals
are drawn by filled circles. .................................................................... 21
Fig. 3: (a) A block graph, and (b) a decomposition tree T* for (a), where a
square represents a block and filled circle indicates a cut vertex. ........ 32
Fig. 4: A block tree TB with root B = B1 for Fig. 3(b). .................................... 33

List of Tables
Table 1: Summary the time complexity results on trees and block graphs…. 16

[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of
Computer Algorithms, Reading, MA, 1974.
[2] H. Aram, S.M. Sheikholeslami, and O. Favaron, Domination subdivision
numbers of trees, Discrete Math. 155 (2007) 1700-1707.
[3] S.R. Arikati and C.P. Rangan, Linear algorithm for optimal path cover
problem on interval graphs, Inform. Process. Lett. 35 (1990) 149-153.
[4] Katerina Asdre, Stavros D. Nikolopoulos, Charis Papadopoulos, An optimal
parallel solution for the path cover problem on P4-sparse graphs, Parallel
Distrib. Comput. 67 (2007) 63 – 76.
[5] R. Bardeli, M. Clausen, and A. Ribbrock, A covering problem that is easy
for trees but NP-complete for trivalent graphs, Discrete Appl. Math. 156
(2007) 2855-2866.
[6] A.A. Bertossi and M.A. Bonuccelli, Hamiltonian circuits in interval graph
generalizations, Inform. Process. Lett. 23 (1986) 195-200.
[7] J.R.S. Blair, W. Goddard, S.T. Hedetniemi, S. Horton, P. Jones, and G.
Kubicki, On domination and reinforcement numbers in trees, Discrete Math.
308 (2008) 1165-1175.
[8] F.T. Boesch and J.F. Gimpel, Covering the points a digraph with
point-disjoint paths and its application to code optimization, J. ACM 24
(1977) 192-198.
[9] G.J. Chang, Corrigendum to: The path-partition problem in block graphs,
Inform. Process. Lett. 83 (2002) 293.
[10] M.S. Chang, S.L. Peng and J.L. Liaw, Deferred-query: an efficient approach
for some problems on interval graphs, Networks 34 (1999) 1-10.
[11] H.H. Chou, M.T. Ko, C.W. Ho, and G.H. Chen, Node-searching problem on
block graphs, Discrete Appl. Math. 156 (2008) 55-75.
[12] P. Damaschke, J.S. Deogun, D. Kratsch and G. Steiner, Finding Hamiltonian
paths in cocomparability graphs using the bump number algorithm, Order 8
(1992) 383-391.
[13] D. Doratha E and S. Hougardy, On approximation algorithms for the
terminal Steiner tree problem, Inform. Process. Lett. 89 (2004) 15-18.
[14] H. Escuadro and P. Zhang, Extremal problems on detectable colorings of
trees, Discrete Math. 308 (2008) 1951-1961.
[15] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the
Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
[16] M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified
NP-complete graph problems, Theoret. Comput. Sci. 1 (1976) 237-267.
[17] S. Goodman and S. Hedetniemi, On the Hamiltonian completion problem,
in: Proc. 1973 Capital Conf. on Graph Theory and Combinatorics, Lecture
Notes in Math. 406 (1974) 262-272.
[18] L.T. Quoc Hung, M.M. Sysło, M.L. Weaver and D.B. West, Bandwidth and
density for block graphs, Discrete Math. 189 (1998) 163-176.
[19] R.W. Hung, A linear-time algorithm for the terminal path cover problem in
cographs, in: Proceddings of the 23rd Workshop on Combinatorial
Mathematics and Computation Theory, Changhwa, Taiwan, (2006) 62-75.
(http://algo2006.csie.dyu.edu.tw/paper/1/B14.pdf)
[20] R.W. Hung, Optimal vertex ranking of block graphs, Information and Computation 206 (2008) 1288-1302
[21] R.W. Hung and M.S. Chang, Solving the path cover problem on circular-arc
graphs by using an approximation algorithm, Discrete Appl. Math. 154
(2006) 76-105.
[22] R.W. Hung and M.S. Chang, Finding a minimum path cover of a
distance-hereditary graph in polynomial time, Discrete Appl. Math. 155
(2007) 2242-2256.
[23] R.W. Hung and C.A. Fang, A linear-time algorithm for the terminal path
cover problem in trees, in: Proceedings of National Computer Symposium
(NCS’2007), Taichung, Taiwan, 2007, 558-566.
[24] R.W. Hung, A linear-time algorithm for the terminal path cover problem in
block graphs, in: International MultiConference of Engineers and Computer
Scientists (IMECS’2008), HonKong, Vol. I., 2008, 286-292.
[25] G. Xu, L. Kang, E. Shan, and M. Zhao, Power domination in block graphs,
Theoret. Comput. Sci. 359 (2006) 299-305.
[26] S. Kenkre and S. Vishwanathan, The common prefix problem on trees,
Inform. Process. Lett. 105 (2008) 245-248.
[27] E. Korach and M. Stern, The complete optimal stars clustering tree problem,
Discrete Appl. Math. 156 (2008) 444-450.
[28] M.S. Krishnamoorthy, An NP-hard problem in bipartite graphs, SIGACT
News 7 (1976) 26.
[29] G. Lin, Z. Cai, and D. Lin, Vertex covering by paths on trees with its
applications in machine translation, Inform. Process. Lett. 97 (2006) 73-81.
[30] S. Moran and Y. Wolfstahl, Optimal covering of cacti by vertex disjoint
paths, Theoret. Comput. Sci. 84 (1991) 179-197.
[31] H. Müller, Hamiltonian circuits in chordal bipartite graphs, Discrete Math.
156 (1996) 291-298.
[32] H. Nagamochi and K. Okada, Approximating the minmax rooted tree cover
in a tree, Inform. Process. Lett. 104 (2007) 173-178.
[33] G. Narasimhan, A note on the Hamiltonian circuit problem on directed path
graphs, Inform. Process. Lett. 32 (1989) 167-170.
[34] S.C. Ntafos and S. Louis Hakimi, On path cover problems in digraphs and
applications to program testing, IEEE Trans. Software Engrg. 5 (1979)
520-529.
[35] J.J Pan and G.J. Chang, Path partition for graphs with special blocks,
Discrete Appl. Math. 145 (2005) 429-436.
[36] S. Pinter and Y. Wolfstahl, On mapping processes to processors, Internat. J.
Parallel Programming 16 (1987) 1-15.
[37] K. Sitaraman, N. Ranganathan, and A. Ejnioui, A VLSI architecture for
object recognition using tree matching, in: Application-Specific Systems,
Architectures and Processors, IEEE International Conference (2002)
325-334.
[38] R. Srikant, R. Sundaram, K.S. Singh and C.P. Rangan, Optimal path cover
problem on block graphs and bipartite permutation graphs, Theoret. Comput.
Sci. 115 (1993) 351-357.
[39] H. Stephen W, On tree congestion of graphs, Discrete Math. 308 (2008)
1801-1809.
[40] A.S. Tanenbaum, Computer Networks, Prentice-Hall, Englewood Cliffs,
1981.
[41] P.K. Wong, Optimal path cover problem on block graphs, Theoret. Comput.Sci. 225 (1999) 163-169.
[42] Q. Wu, C.L. Lu, and R.C.T. Lee, The approximability of the weighted
Hamiltonian path completion problem on a tree, Theoret. Comput. Sci. 341
(2005) 385-397.
[43] Bang-YeWu, Hung-Lung Wang, Shih Ta Kuan, Kun-Mao Chao, On the
uniform edge-partition of a tree, Discrete Applied Mathematics 155 (2007)
1213 – 1223.
[44] J.H. Yan and G.J. Chang, The path-partition problem in block graphs,
Inform. Process. Lett. 52 (1994) 317-322.
[45] J.H. Yan, G.J. Chang, S.M. Hedetniemi, and S.T. Hedetniemi, k-path
partitions in trees, Discrete Appl. Math. 78 (1997) 227-233.
[46] H.G. Yeh and G.J. Chang, The path-partition problem in bipartite
distance-hereditary graphs, Taiwanese J. Math. 2 (1998) 353-360.
[47] William C.K. Yen, The bottleneck independent domination on the classes of
bipartite graphs and block graphs, Inform. Sci. 157 (2003) 199-215.