簡易檢索 / 詳目顯示

研究生: 謝宗麟
Chung-Lin Hsieh
論文名稱: 在特殊圖上一些問題的平行演算法設計及分析
The Designs and Analyses of Parallel Algorithms for Some Problems on Special Graphs
指導教授: 林順喜
Lin, Shun-Shii
學位類別: 碩士
Master
系所名稱: 資訊教育研究所
Graduate Institute of Information and Computer Education
畢業學年度: 87
語文別: 中文
論文頁數: 86
中文關鍵詞: 區間圖環弧圖橋接線問題切點問題連通元件問題二元連通元件問題擴張樹問題常數時間演算法
英文關鍵詞: interval graphs, circular-arc graphs, bridge problem, articulation point problem, connected component problem, biconnected component problem, spanning tree problem, constant-time algorithm
論文種類: 學術論文
相關次數: 點閱:358下載:0
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 具有可重組態匯流排系統之處理器陣列(Processor Arrays with Reconfigurable Bus Systems,簡稱PARBS)為一種平行處理的計算模型,它具有一個處理器陣列和一個可重組態匯流排系統。在此模型中,我們可以任意地動態設定所有處理器的組態,進而將其處理器陣列切割成不同的子網路,在子網路中我們可以做快速的資料傳輸動作,於是便有許多研究者在此平行計算模型上發展有效率或常數時間的平行演算法,以解決許多複雜的問題。
    在本篇論文中,我們提出一個嶄新的、在一般圖中尋找橋接線的演算法。我們的演算法可以在O(1)時間內使用3D-O(n^3)或2D-O(n^4)個處理器的PARBS來解決這個問題。此外,我們在區間圖及環弧圖中也發展出尋找連通元件、切點、橋接線、二元連通元件和擴張樹的演算法,這些問題均可在O(1)的時間內,用2D-O(n^2)個處理器的PARBS來解決。

    A processor array with reconfigurable bus system (abbreviated to PARBS) is a parallel computation model that consists of a processor array and a reconfigurable bus system. In this model, we can dynamically setup the configurations of all processors in order to form different sub-buses in the processor array. There are a lot of researchers that develop efficient or constant-time algorithms based on this parallel computation model in order to solve many complicated problems, because in a sub-bus the data can be broadcasted in fixed units of time.
    In this thesis, we will propose a new algorithm to find all bridges of a general graph in O(1)-time on a 3D-O(n^3) or 2D-O(n^4) PARBS. We also develop some related graph algorithms to find all connected components, articulation points, bridges, biconnected components and a spanning tree of an interval graph or a circular graph in O(1)-time on a 2D-O(n^2) PARBS.

    第一章 緒論(1) 1.1 簡介 (1) 1.2 文獻探討(5) 1.3 本篇論文的結構(8) 第二章 問題定義與我們所用的PARBS模型(9) 2.1 我們所用的PARBS模型(9) 2.2 本論文所使用之圖形名詞的定義(12) 第三章 一般圖中尋找橋接線的常數時間演算法(19) 第四章 區間圖上一些問題之常數時間演算法(37) 4.1 區間圖的定義與性質(37) 4.2 區間圖上連通性測試與尋找連通元件演算法(40) 4.3 區間圖上尋找切點演算法(47) 4.4 區間圖上尋找橋接線演算法(52) 4.5 區間圖上尋找二元連通元件演算法(58) 4.6 區間圖上尋找擴張樹演算法(62) 第五章 環弧圖上一些問題之常數時間演算法(65) 5.1 環弧圖的定義與性質(66) 5.2 環弧圖上連通性測試與尋找連通元件演算法(69) 5.3 環弧圖上尋找切點演算法(75) 5.4 環弧圖上尋找橋接線演算法(76) 5.5 環弧圖上尋找二元連通元件演算法(77) 5.6 環弧圖上尋找擴張樹演算法(78) 第六章 結論(79) 第七章 參考文獻(83)

    【1】 Arvind, K., Kamakoti, K. A., and Rangan, C. P., “Efficient Parallel Algorithms for Permutation Graphs,” Journal of Parallel and Distributed Computing 26, pp. 116-124(1995).
    【2】 Atallah, M. J., and Kosaraju, S. R., “Graph Problems on a Mesh-Connected Processor Array,” Journal of the Association for Computing Machinery. Vol. 31, No. 3, pp. 649-667(1984).
    【3】 Bertossi, A. A., and Moretti, S., “Parallel Algorithms on Circular-Arc Graphs,” Information Processing Letters 33, pp. 275-281(1989/90).
    【4】 Chen, G. H., and Liang, W. W., “Conflict-free broadcasting algorithms for graph traversals and their applications,” Parallel Computing 18, pp. 439-448(1992).
    【5】 Cormen, T., Leiserson, C. E., and Rivest, R. L., Introduction to Algorithms, McGraw-Hill Book Company.(1989)
    【6】 Das, S. K., and Chen, C. C.-Y., “Efficient Parallel Algorithms for Computing Articulation Points and Bridges of Interval Graphs,” 1992 International Conference on Parallel Processing. Vol. 3, pp. 164-167(1992).
    【7】 Gazit, H., “An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph,” SIAM J. Comput. Vol. 20, No. 6, pp. 1046-1067(1991).
    【8】 Hsu, S. C., Hsieh, H. F., and Huang, S. T., “A fullly-pipelined systolic algorithm for finding bridges on a undirected connected graph,” Parallel Computing 18, pp. 377-391(1992).
    【9】 Hsu, T. S., and Ramachandran, V., “Finding a smallest augmentation to biconnect a graph,” SIAM J. Comput. Vol. 22, No. 5, pp. 889-912(1993).
    【10】 Ibarra, O. H., and Zheng, Q., “Finding Articulation Points and Bridges of Permutation Graphs,” 1993 International Conference on Parallel Processing. Vol. 3, pp. 77-80(1993).
    【11】 Jang, J. W., and Prasanna V. K., “An Optimal Sorting Algorithm on Reconfigurable Mesh,” Journal of Parallel and Distributed Computing. Vol. 25, No. 1, pp. 31-41(1995).
    【12】 Kao, T. W., and Horng S. J., “Optimal Algorithms for Computing Articulation Points and Some Related Problems on a Circular-Arc Graph,” Parallel Computing 21, pp. 953-969(1995).
    【13】 Kao, T. W., Horng, S. J., and Tsai, H. R., “Computing Connected Components and Some Related Applications on a RAP,” 1993 International Conference on Parallel Processing. Vol. 3, pp. 57-64(1993).
    【14】 Kumar, V., Grama, A., Gupta, A., and Karypis, G., Introduction to Parallel Computing : Design and Analysis of Algorithms, The Benjamin/Cummings Publishing Company, INC.(1994)
    【15】 Laumond, J. P., “Connectivity of Plane Triangulations,” Information Processing Letters 34, pp. 87-96(1990).
    【16】 Laumond, J. P., “Enumeration of Articulation Pairs of a Planar Graph,” Information Processing Letters 21, pp. 173-179(1985).
    【17】 Lin, S. S., “Cost-Effective Algorithms for Processor Arrays with Reconfigurable Bus System,” Journal of the Chinese Institute of Engineers. Vol. 17, No. 2, pp. 279-288(1994).
    【18】 Merry, M. S., and Baker, J., “A Constant Time Sorting Algorithm for a Three Dimensional Reconfigurable Mesh and Reconfigurable Network,” Parallel Processing Letters. Vol. 5, No. 3, pp. 401-412(1995).
    【19】 Miller, R., Prasanna-Kumar, V. K., Reisis, D., and Stout, Q., “Parallel computations on reconfigurable meshes,” IEEE Trans. Comput. 42. pp. 678-692(1993).
    【20】 Nigam, M., and Sahni, S., “Sorting n Numbers on n×n Reconfigurable Meshes with Buses,” Journal of Parallel and Distributed Computing 23, pp. 37-48(1994).
    【21】 Olariu, S., Schwing, J. C., and Zhang, J., “Applications of Reconfigurable Meshes to Constant-Time Computations,” Parallel Computing. Vol. 19, No. 2, pp. 229-237(1993).
    【22】 Pan, T. T., and Lin, S. S., “Constant-Time Algorithms for Minimum Spanning Tree Problem on Processor Arrays with Reconfigurable Bus Systems,” Master Thesis, The National Taiwan Normal University, Taiwan, R.O.C.(1998).
    【23】 Rao, A. S., and Rangan, C. P., “Optimal Parallel Algorithms on Circular-Arc Graphs,” Information Processing Letters 33, pp. 147-156(1989).
    【24】 Sprague, A. P., and Kulkarni, K. H., “Optimal Parallel Algorithms for Finding Cut Vertices and Bridges of Interval Graphs,” Information Processing Letters 42, pp. 229-234(1992).
    【25】 Subbaraman, C. P., Trahan, J. L., and Vaidyanathan, R., “List Ranking and Graph Algorithms on the Reconfigurable Multiple Bus Machine,” 1993 International Conference on Parallel Processing. Vol. 3, pp. 244-247(1993).
    【26】 Trahan, J. L., Vaidyanathan, R., and Subbaraman, C. P., “Constant Time Graph Algorithms on the Reconfigurable Multiple Bus Machine,” Journal of Parallel and Distributed Computing 46, pp. 1-14(1997).
    【27】 Tsai, H. R., Horng, S. J., Tsai, S. S., Kao, T. W., and Lee, S. S., “Solving an Algebraic Path Problem and Some Related Graph Problems on a Hyper-Bus Broadcast Network,” IEEE Transactions on Parallel and Distributed Systems. Vol. 8, No. 12, pp. 1226-1235(1997).
    【28】 Wang, B. F., and Chen, G. H., “Constant Time Algorithms for the Transitive Closure and Some Related Graph Problems on Processor Arrays with Reconfigurable Bus System,” IEEE Transactions on Parallel and Distributed Systems. Vol. 1, No. 4, pp. 500-507(1990).
    【29】 Wang, B. F., Chen, G. H., and Lin, F. C., “Constant Time Sorting on a Processor Array with a Reconfigurable Bus System,” Information Processing Letters, Vol. 34, No. 4, pp. 187-192(1990).
    【30】 Wang, B. F., Lu, C. J., and Chen, G. H., “The Algebraic Path Problem on Processor Arrays with Reconfigurable Bus System,” IEEE Transactions on Parallel and Distributed Systems, Vol. 3, No. 2, pp. 251-256(1992).
    【31】 Yang, C. B., Lee, R. C. T., and Chen, W. T., “Parallel Graph Algorithms Based upon Broadcast Communications,” IEEE Trans. Computers, Vol. 39, No. 12, pp. 1468-1472(1990).

    無法下載圖示
    QR CODE