The performance of multilective VLSI algorithms

DOI10.1016/0022-0000(84)90033-3zbMath0583.68021OpenAlexW2083381826MaRDI QIDQ1069297

John E. Savage

Publication date: 1984

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(84)90033-3

zbMATH Keywords

lower boundsarea-time productsmultilective algorithmsplanar circuit size

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Communication Complexity and Lower Bounds on Multilective Computations, Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits, Planar acyclic computation, On the complexity of planar Boolean circuits, Two tapes versus one for off-line Turing machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Area-time optimal VLSI networks for multiplying matrices
• Area-time tradeoffs for matrix multiplication and related problems in VLSI models
• Space-Time Trade-Offs for Banded Matrix Problems
• Information transfer and area-time tradeoffs for VLSI multiplication
• A Separator Theorem for Planar Graphs
• The Area-Time Complexity of Binary Multiplication
• Space-time trade-offs on the FFT algorithm
• Computational Work and Time on Finite Machines