The VLSI Complexity of Selected Graph Problems
Joseph Já Já · Journal of the ACM · 1984
General lower bound techniques are developed to determine the VLSI complexity of graph problems with some surprising results that show a striking difference between this class of problems and the other classes studied in the literature.The results show that the VLSI complexity of graph problems depends crucially on several parameters such as the I/O formats, the locaUons of the I/O ports, and the Umlng of the I/O bits Almost all of our lower bounds can be matched with existing upper bounds or bounds obtained by some minor modificatmns of existing algorithms Categories and SubJect Descriptors: B.7.1 [