CONSTANT-TIME ALGORITHMS FOR GRAPH CONNECTIVITY PROBLEMS ON RECONFIGURABLE MESHES USING FEWER PROCESSORS

This paper makes an efficient improvement of processor complexity whil e solving some connectivity problems on a reconfigurable meshes. We fi rst derive two constant time algorithms in the proposed parallel proce ssing system for computing the dominators and the dominator tree of an undirected graph either using a 3-D n x n x n processors or a 2-D n(2 ) x n(2) processors, where n is the number of vertices of the graph. T hen based on the dominator tree algorithm, we also solve many other gr aph connectivity problems in a constant time. They are the articulatio n paints, bridges, biconnected components, and bridge-connected compon ents problem in undirected graphs.