可重組態匯流排系統是一種組態可以動態改變的匯流排系統。在這種模型上，許多
問題可以在固定的時間內完成。這些問題包括ｎ位元做互斥或運算、ｎ位元求和、
ｎ個ｍ位元的整數求和、兩個ｎ位元的整數相乘、決定無向圖的連通元件、計算無
向圖的遞移包矩陣、辨認二分圖、尋找無向圖的連通元件、有關接合點的問題、有
關雙連通元件的問題、有關橋的問題、無向圖中最小生成樹的問題、排序問題、以
及convex hull 問題。
在這篇論文中，我們提出一些最佳成本的演算法。這些問題包括在可重組態線型陣
列中從ｎ個元素的已序序列中建造２－３樹，可在固定的時間內完成；而所需的處
理機數目為ｎ。在這個演算法之上，有許多的基本運算，例如插入一個新的元素、
刪除一個元素、找尋特定元素等。此外，我們也利用可重組態線型陣列來選擇第ｋ
小的元素、刪除最小（最大）的元素（以模擬優先順序佇列）。
另一個問題是選擇問題，選擇問題是找ｎ個元素中第ｋ小的元素。在這篇論文中我
們提供一個對於未序序列的選擇問題的演算法，所使用的計算模型為一維的可重組
態線型陣列模型，以及二維的可重組態RMESH 模型。所需的時間為O(logn) ；而
所需的處理機數目為ｎ。
本論文的結構如下：第一章為介紹，將介紹目前在此模型上所發展出的演算法。第
二章中將描述在這篇論文中所使用的計算模型；可重組態線型陣列模型和可重組態
RMESH 模型，以及在這篇論文中所用到的一些基本運算。第三章中將介紹建造２－
３樹的演算法，以及其他的基本運算。第四章將介紹選擇問題。