具有可重組態匯流排系統之處理器陣列(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).