# 臺灣博碩士論文加值系統

(44.211.84.185) 您好！臺灣時間：2023/05/30 06:23

:::

### 詳目顯示

:

• 被引用:0
• 點閱:132
• 評分:
• 下載:10
• 書目收藏:0
 一個圖形的生成樹是一個包含原圖上所有點的連通樹。 目前有各種不同的生成樹問題如最小生成樹、最小直徑生成樹，與類似生成樹概念的最小史坦納樹等問題，在現實中都有重要應用。在這篇論文中，我們提出一個新的生成樹問題，稱為強壯生成樹問題。並提出多項式時間的演算法在一些特殊圖形解決這個問題，這些圖形包括區塊圖，探針區塊圖和仙人掌圖。
 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 thisproblem on some special classes of graphs, e.g., block graphs, probe block graphs, and cactus graphs.
 Abstract iContents iiList of Figures iii1 Introduction 12 Preliminaries 53 Our Algorithms 114 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)
 電子全文
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 最小分級生成樹問題之研究 2 最長路徑問題在一些類樹圖之研究

 1 陳秀珠、李景美（1999）。老人運動行為研究──以北市基督長老教會松年大學五十五歲以上學員為例。健康促進暨衛生教育雜誌，19，1-12。 2 張雅文（2012）。充實知識見聞提升教學創意。國教新知，59（1），103-106。 3 張雅文（2012）。充實知識見聞提升教學創意。國教新知，59（1），103-106。 4 張家倩（2000）。從「教育原住民」邁向「原住民教育」──以澳洲原住民成人教育為例。原住民教育季刊，17，7-15。 5 張家倩（2000）。從「教育原住民」邁向「原住民教育」──以澳洲原住民成人教育為例。原住民教育季刊，17，7-15。 6 高鵬（2012）。「推動社會教育、提倡終身學習、促進保存文化」之成果與未來努力方向。全國新書資訊月刊，159，4-9。 7 高鵬（2012）。「推動社會教育、提倡終身學習、促進保存文化」之成果與未來努力方向。全國新書資訊月刊，159，4-9。 8 高德義（1998）。打造原住民教育的新希望—淺談原住民終身學習體系的建構。社教雙月刊，88，21-25。 9 高德義（1998）。打造原住民教育的新希望—淺談原住民終身學習體系的建構。社教雙月刊，88，21-25。 10 高翠霞、蔡崇建、莊潔（2011）。臺灣國民小學學校閒置空間 現況、問題與對策。教育資料集刊，49，31-68。 11 高翠霞、蔡崇建、莊潔（2011）。臺灣國民小學學校閒置空間 現況、問題與對策。教育資料集刊，49，31-68。 12 翁麗芳（1995）。臺灣基督長老教會的教育工作。國立中央圖書館臺灣分館館刊，1（4），72-88。 13 翁麗芳（1995）。臺灣基督長老教會的教育工作。國立中央圖書館臺灣分館館刊，1（4），72-88。 14 徐敏雄（1999）。宗教團體的社會教育活動－臺灣基督長老教會臺北婦女展業中心。社教雙月刊，90，50-52。 15 徐敏雄（1999）。宗教團體的社會教育活動－臺灣基督長老教會臺北婦女展業中心。社教雙月刊，90，50-52。

 1 臺灣的煙草產業與區域發展 以花蓮鳳林為個案 2 新北市新莊副都心發展歷程下的住宅空間生產 3 慈濟在莫拉克風災中救災行動之研究 4 利用巢狀式變動鄰域搜尋法求解平行機台排程與途程規劃之整合問題 5 服務導向鐵公路複合運輸物流轉運系統之派遣決策問題 6 找自己的路：一位vusam眼中的排灣族婚禮演變 7 多孔性氧化鋅披覆碳纖維複合材料之製備與抗菌特性暨光催化生質燃料製氫研究 8 低碳旅遊休閒效益與願付價值之研究 9 以推拉因子探討國際賞鳥客之旅遊行為 10 觀想─蕭興宇創作自述 11 改變中英茶葉貿易的科學調查──植物獵人福瓊(Robert Fortune)的茶樹調查與移植 12 黨同伐異：「反革命罪」及其爭議（1927-1931） 13 脈波訊號分析於人體臨床應用及大鼠模型之研究 14 設計具有節能效益之遲滯電流控制器於感應馬達驅動系統 15 高台著地與高台著地反彈跳動作下肢負荷與生物力學特性

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室