研究生: |
謝宗麟 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】 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).