The complexity of graph problems on vlsi
Susanne E. Hambrusch · 1982
We study VLSI solutions to a number of graph problems including finding the connected components, the biconnected and bridgeconnected components, the minimum spanning tree and the strongly connected components. We present primarily results for undirected problems on chips of small area: i.e., area too small to store the edges of the graph explicitly within the chip for the entire computation. All undirected graph problems we consider can be solved on chips of (CIRCLE)(n) area, where n is the number of vertices in the graph, whereas the directed problems require (OMEGA)(n('2)) area. Small area is interesting from a practical point of view because the actual design of small chips can be attempted. We develop a new lower bound technique that gives good lower bounds on the time needed to solve undirected graph problems on chips of small, o(n('2)), area. The bounds hold in the when-oblivious model (when the chip is not able to determine the time of the arrival of the next input wave), and with the graph given in the form of adjacency lists or edges. The technique combines an adversary, and information flow and Kolmogorov complexity arguments. It extends previous techniques to a more dynamic setting, where new information becomes available during the computation. One consequence of our lower bound results is that the time needed to solve undirected graph problems on a linear array of n processing elements is (OMEGA)(n('2)). Matching upper bounds can be achieved for the connected component and spanning tree problem. We present when oblivious as well as not when oblivious algorithms for a number of undirected graph problems. It appears that efficient when-oblivious algorithms are harder to find than not-when oblivious ones. Furthermore it appears that input in the form of adjacency lists and edges is harder to handle than input in the form of an adjacency matrix. Most of the algorithms for the undirected problems are implemented on 2-dimensional meshes of O(n) area, which are very suitable for direct hardware implementation. The algorithms can be generalized to run on d-dimensional meshes, where d can be any real number (GREATERTHEQ) 2. This yields a continuous tradeoff of AT('2) = O(n('4)) in the range (OMEGA)(n) = A = o(n('2)).