摘 要
在排列圖及區間圖上一些問題的平行演算法設計及分析
具有可重組態匯流排系統之處理器陣列 (Processor Arrays with Reconfigurable Bus Systems，簡稱PARBS) 為一種平行處理的計算模型，它具有一個處理器陣列和一個可重組態匯流排系統。在此模型中，我們可以動態地調整所有處理器的組態，進而將整個處理器陣列切割成不同的子網路，在子網路上我們可以做快速的資料傳輸動作，於是便有許多研究者在此平行計算模型上發展平行演算法，以解決許多複雜的問題。
在本篇論文中，我們設計出利用O(p)個處理器的一維PARBS在O(n/p + log p)的時間內計算出前置最大值、後置最小值和前置和的演算法。另外，我們也發展出一個可以在O(n/p)的時間內利用O(p)個處理器來過濾一個非遞減數列中的重覆資料演算法。
在排列圖上，我們發展出連通測試、尋找連通元件、尋找切點和尋找擴張樹的演算法；在區間圖上，我們發展出連通測試、尋找連通元件、尋找切點、尋找橋接線和尋找擴張樹的演算法。這些問題均可以在O(n/p + log p)的時間內，利用O(p)個處理器的一維PARBS來解決。上述的所有演算法，當p = O(n/log n)時，整個演算法的計算成本均可以達到成本最佳化。
關鍵字：可重組態匯流排系統之處理器陣列、成本最佳化演算法、前置最大值、後置最小值、前置和、過濾非遞減數列重覆資料、排列圖、區間圖、連通測試問題、連通元件問題、切點問題、橋接線問題、擴張樹問題

ABSTRACT
The Designs and Analyses of Parallel Algorithms for Some
Problems on Permutation and Interval Graphs
A processor array with reconfigurable bus system (abbreviated to PARBS) is a parallel computation model that consists of 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. In a sub-bus, the data can be broadcasted in fixed units of time. There are a lot of researchers that develop parallel algorithms on this computation model in order to solve many complicated problems.
In this thesis, we propose algorithms for computing prefix maxima, suffix minima and prefix sum in O(n/p+log p) time on a 1D PARBS with O(p) processors. We also design an algorithm to filter out duplicate data in a nondecreasing sequence in O(n/p) time on a 1D PARBS with O(p) processors.
In addition, we develop algorithms for finding all connected components, articulation points, and a spanning tree of a permutation graph. We also develop algorithms for finding all connected components, articulation points, bridges, and a spanning tree of an interval graph. These algorithms take O(n/p + log p) time on a 1D PARBS with O(p) processors. If p = O(n/log n), they all become cost optimal.
Keyword: PARBS (Processor Arrays with Reconfigurable Bus Systems), cost optimal algorithm, prefix maxima, suffix minima, prefix sum, filter out duplicate data, permutation graph, interval graph, connectivity test problem, connected component problem, articulation point problem, bridge problem, spanning tree problem.

[1] Akl, S. G., Parallel computation - Models and Methods, Prentice-Hall Inc.,New Jersey, (1997).
[2] Arvind, K., Kamakoti, V., and Rangan, C. P., "Efficient parallel algorithms for permutation graphs," Journal of Parallel and Distributed Computing, vol. 26, pp. 116-124, (1995).
[3] 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).
[4] Bodlaender, H., Kloks, T., and Kratsch, D., "Treewidth and pathwidth of permutation graphs," SIAM Journal on Discrete Mathematics, vol. 8, no. 4, pp. 606-616, (1996).
[5] Chao, H. S., Hsu, F. R., and Lee, R. C. T., "An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs," Information Processing Letters, vol. 61, no. 6, pp. 311-316, (1997).
[6] Chen, Y. W., Horng, S. J., Kao, T. W., Tsai, H. R., and Tsai, S. S., "Parallel connectivity algorithms on permutation graphs," Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, pp. 97-104, (1994).
[7] Cormen, T., Leiserson, C. E., and Rivest, R. L., Introduction to Algorithms, McGraw-Hill Book Company, New York, (1996).
[8] 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).
[9] Golumbi, M. C., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, (1980).
[10] Hsieh, C. L., "The designs and analyses of parallel algorithms for some problems on special graphs," Master Thesis, The National Taiwan Normal University, Taiwan, R.O.C., (1999).
[11] Ibarra, O. H., and Zheng, Q., "Finding articulation points and bridges of permutation graphs," International Conference on Parallel processing, vol. 3, pp. 77-80, (1993).
[12] Ibarra, O. H., and Zheng, Q., "An optimal shortest-path parallel algorithm for permutation graphs," Journal of Parallel and Distributed Computing, vol. 24, no. 1, pp. 94-99, (1995).
[13] Jaja, J., An Introduction to Parallel Algorithms, Addison-Wesley Publishing Company Inc., New York, (1992).
[14] 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).
[15] Kao, T. W., and Horng, S. J., "Optimal algorithms for computing articulation points and some related problems on circular-arc graph," Parallel Computing, vol. 21, pp. 953-969 (1995).
[16] Kruskal, C. P., Rudolph, L., and Snir, M., "The power of parallel prefix," IEEE Transactions On Computers, vol. c-34, no. 10, pp. 965-968, (1985).
[17] Kumar, V., Grama, A., Gupta, A., and Karypis, G., Introduction to Parallel Computing: Design and Analysis of Algorithms, The Benjamin/Cummings Publishing Company, Inc., California, (1994).
[18] Liang, Y. D., "On the feedback vertex set problem in permutation graphs," Information Processing Letters, vol. 52, no. 3, pp. 123-129, (1994).
[19] Liang, Y. D., and Rhee, C., "An optimal algorithm for finding biconnected components in permutation graph," Proceedings of the 1995 ACM 23rd annual computer science conference on Computer science conference, pp.104-108, (1995).
[20] Lin, R., Olariu, S., Schwing, J. L., and Zhang, J., "Computing on reconfigurable buses - A new computational paradigm," Parallel Processing Letters, vol. 4, no. 4, pp. 465-476, (1994).
[21] Miller, R., Kumar, V. K. P., Reisis, D., and Stout, Q. F., "Meshes with reconfigurable buses," Proceedings of the Fifth MIT Conference on Advanced Research in VLSI, pp. 163-178, (1988).
[22] Nigam, M., and Sahni, S., "Sorting n numbers on n ’ n Reconfigurable Meshes with Buses," Journal of Parallel and Distributed Computing, vol. 23, pp. 37-48, (1994).
[23] Pan, T. T., "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).
[24] Ramkumar, G. D. S., and Pandu Rangan, C., "Parallel algorithms on interval graphs," Proceedings of the International Conference on Parallel Processing, vol. 3, pp. 72-74, (1990).
[25] Rhee, C., Liang, Y. D., Dhall, S. K., and Lakshmivarahan, S., "Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs," Information Process Letter, vol. 49, pp. 45-50, (1994).
[26] Sprague, A. P., and Kulkarni, K. H., "Optimal parallel algorithms for finding cut vertices and bridges of interval graphs," Information Processing Letters, vol. 42, pp. 229-234, (1992).
[27] Wang, B. F., and Chen G. H., "Two-dimensional processor array with a reconfigurable bus system is at least as powerful as the CRCW model," Information Processing Letters, vol. 36, no.1 pp.31-36, (1990).
[28] Wang, B. F., and Chen, G. H., "Configurational computation: A new algorithm design strategy on processor arrays with reconfigurable bus systems,", Doctor Thesis, The Taiwan university, Taiwan, R.O.C., (1991).
[29] Wang, Y. L., Chen, H. C., and Lee, C. Y., "An O(log-n) parallel algorithm for constructing A spanning tree on permutation graphs," Information Processing Letters, vol. 56, no.2, pp. 83-87, (1995).
[30] Yeh, C. H., and Parhami, B., "New representation of graphs and its applications to parallel processing," Proceedings of the 1998 International Conference on Parallel and Distributed Systems, pp. 702-709, (1998).
[31] Yu, C. W., and Chen, G. H., "An efficient parallel recognition algorithm for bipartite-permutation graphs," IEEE Transactions on Parallel and Distributed Systems, vol. 7, no. 1, pp. 3-10 (1996).