臺灣博碩士論文加值系統

一個圖形的生成樹是一個包含原圖上所有點的連通樹。 目前有各種不同的生成樹問題如最小生成樹、最小直徑生成樹，與類似生成樹概念的最小史坦納樹等問題，在現實中都有重要應用。在這篇論文中，我們提出一個新的生成樹問題，稱為強壯生成樹問題。並提出多項式時間的演算法在一些特殊圖形解決這個問題，這些圖形包括區塊圖，探針區塊圖和仙人掌圖。

A spanning tree of an unweighted graph is a tree containing all the vertices of the graph. There are many variants of spanning tree problem, namely, minimum spanning tree problem, minimum diameter spanning tree problem, minimum steiner tree problem, and so on. In this thesis, we propose a new variant called the robustness spanning tree problem. Then we present polynomial-time algorithms for solving this
problem on some special classes of graphs, e.g., block graphs, probe block graphs, and cactus graphs.

Abstract i
Contents ii
List of Figures iii
1 Introduction 1
2 Preliminaries 5
3 Our Algorithms 11
4 Conclusion 19

[1] D. Binkele-Raible and H. Fernau, A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem, Lecture Notes in Computer Science, Vol. 6072, pp. 328-339 (2010)
[2] R. E. Burkard , Y. Lin and G. Rote, The Obnoxious Center Problem on a Tree, SIAM Journal on Discrete Mathematics, Vol. 14, pp. 498-509 (2001)
[3] B. Ben-moshe, B. Bhattacharya and Q. Shi, Ecient Algorithms for The Weighted 2-center Problem in a Cactus Graph, Lecture Notes in Computer Science, Vol. 3827, pp. 693-703 (2005)
[4] A. Caldwell, A. B. Kahng, S. Mantik, I. Markov, and A. Zelikovsky, On Wirelength Estimations for Row-Based Placement, International Symposium on Physical Design, pp. 4-11 (1998)
[5] W. Chou and A. Kershenbaum, A Unied Algorithm for Designing Multidrop Teleprocessing Networks, Proceedings of the third ACM symposium on Data communications and Data networks: Analysis and Design, pp. 148-156 (1973)
[6] D. Cieslik, Steiner Minimal Trees, Kluwer Academic Publishers, The Netherlands (1998)
[7] X. Cheng and D.-Z. Du, Steiner Trees in Industry, Kluwer Academic Publishers,The Netherlands (2001)
[8] D. Cieslik, The Steiner Ratio, Kluwer Academic Publishers, The Netherlands (2001)
[9] D.-Z. Du, J. M. Smith, and J. H. Rubinstein, Advances in Steiner Trees, Kluwer Academic Publishers, The Netherlands (2000)
[10] J. A. Dei Rossi, R. S. Heiser and N. S King, A Cost Analysis of Minimum Distance TV Networking for Broadcasting Medical Information, RM-6204-NLM, Rand Corporation (1970)
[11] L. R. Esau and K. C. Williams, On Teleprocessing System Design: Part II, IBM Systems Journal, Vol. 5, pp. 142-147 (1966)
[12] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, NY, USA (1979)
[13] S. Guha and S. Khuller, Approximation Algorithms for Connected Dominating Sets, Proceedings of the Fourth Annual European Symposium on Algorithms, Vol. 20, pp. 374-387 (1998)
[14] R. Hassin and A. Tamir, On The Minimum Diameter Spanning Tree Problem, Information Processing Letters, Vol. 53, pp. 109-111 (1998)
[15] A. O. Ivanov and A. A. Tuzhilin, Minimal Networks: The Steiner Problem and Its Generalizations, CRC Press, Boca Raton, Florida (1994)
[16] B. Li and M. Toulouse, Maximum Leaf Spanning Tree Problem for Grid Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 73, pp. 181-193 (2010)
[17] T. Fujie, An Exact Algorithm for The Maximum Leaf Spanning Tree Problem, Journal Computers and Operations Research, Vol. 30, pp. 1931-1944 (2003)
[18] E. Nardelli, G Proietti1 and Peter Widmayer, Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures, Lecture Notes in Computer Science, Vol. 1461, pp. 55-66 (1998)
[19] G. Robins and A. Zelikovsky, Minimum Steiner Tree Construction, The Handbook of Algorithms for VLSI Physical Design Automation, Chapter 24, pp. 487-508, CRC Press (2009)
[20] C. Payan, M. Tchuente, and N. H. Xuong, Arbres avec un Nombres Maximum de Sommet Pendants , Discrete Mathematics, Vol. 49, pp. 267-273 (1984)
[21] J. A. Storer, Constructing Full Spanning Trees for Cubic Graphs, Computers and Operations Research, Vol. 13, pp. 8-11 (1981)
[22] S. Solis-Oba, 2-approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves, Lecture Notes in Computer Science, Vol. 1461, pp. 441-452 (1998)
[23] R. G. Saltman, G. R. Bolotsky and Z. G. Ruthberg, Heuristic Cost Optimization of The Federal Telpaknetwork, Tech. Note 787, National Bureau of Standards, Washington, D.C. (1973)
[24] A. Tamir, Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Date Structures, SIAM Journal of Disrete Mathematics, Vol. 1, pp. 377-396 (1988)