New lower bound techniques for VLSI
- 1 October 1981
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 1-12
- https://doi.org/10.1109/sfcs.1981.22
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