To search, Click below search items.


All Published Papers Search Service


An Efficient List-Ranking Algorithm on a Reconfigurable Mesh with Shift Switching


Young-Hak Kim


Vol. 7  No. 6  pp. 209-214


The parallel list-ranking is a difficult problem because of its extreme sequential property and irregularity. Given a linked list of n nodes, the proposed algorithm runs in O(1) time on the reconfigurable mesh of size nⅹn with shift switching. We improve the time complexity by a factor of O(logn/loglogn) as compared to the previous result using the same architecture. Our result also is improved over a logarithm factor in AT2 as compared to the previous algorithms using two dimensional processor arrays with reconfigurable buses.


List ranking, Reconfigurable mesh/bus, Shift switching