Solving Undirected Graph Problems on VLSI

摘要

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 for a number of other undirected graph problems. Keywords include: VLSI complexity, Lower bound techniques, Information theoretic arguments, and Graph problems.