New lower bound techniques for VLSI
- 1 October 1981
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In this paper, we use crossing number and wire area arguments to find lower bounds on the layout area and maximum edge length of a variety of computationally useful networks. In particular, we describe 1) an N-node planar graph which has layout area Θ(NlogN), and maximum edge length Θ(N1/2/log1/2N), 2) an N-node graph with an O(N1/2)-separator which has layout area Θ(Nlog2N) and maximum edge length Θ(N1/2logN/loglogN), and 3) an N-node graph with an O(N1-1/r)-separator which has maximum edge length Θ(N1-1/r) for any r ≥ 3.Keywords
This publication has 12 references indexed in Scilit:
- A Combinatorial Limit to the Computing Power of VLSI CircuitsIEEE Transactions on Computers, 1983
- Area—time tradeoffs for matrix multiplication and related problems in VLSI modelsJournal of Computer and System Sciences, 1981
- A model of computation for VLSI with related complexity resultsPublished by Association for Computing Machinery (ACM) ,1981
- Bounds on minimax edge length for complete binary treesPublished by Association for Computing Machinery (ACM) ,1981
- The VLSI Complexity of SortingPublished by Springer Nature ,1981
- Area-time optimal VLSI networks for multiplying matricesInformation Processing Letters, 1980
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Area-time complexity for VLSIPublished by Association for Computing Machinery (ACM) ,1979
- Bounds to Complexities of Networks for Sorting and for SwitchingJournal of the ACM, 1975
- The crossing number of K5,nJournal of Combinatorial Theory, 1970