Solving Undirected Graph Problems on VLSI
Susanne E. Hambrusch, Janoš Šimon · SIAM Journal on Computing · 1985
We study VLSI solutions to the connected component problem on networks that have area too small to store all the edges of the graph for the entire computation. We give lower bounds on the time needed to solve this problem on such networks, as well as an optimal algorithm. The lower bounds use a new proof technique combining adversary strategy, information flow, and Kolmogorov complexity arguments. The lower bounds obtained for the connected components problem hold for a number of other undirected graph problems.