Area-time lower-bound techniques with applications to sorting

DOI10.1007/BF01840437zbMath0622.68044MaRDI QIDQ1091139

Franco P. Preparata, Gianfranco Bilardi

Publication date: 1986

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

sortinginformation exchangelower boundsarea-time complexity of VLSI computationscomputational frictionsquare-tessellation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Cellular automata (computational aspects) (68Q80)

Related Items (10)

The area-time complexity of the VLSI counter ⋮ Lower bounds to processor-time tradeoffs under bounded-speed message propagation ⋮ On problem transformability in VLSI ⋮ On the VLSI complexity of some arithmetic and numerical problems ⋮ On the expansion and diameter of bluetooth-like topologies ⋮ The area-time complexity of the greatest common divisor problem: A lower bound ⋮ Optimal tradeoffs for addition on systolic arrays ⋮ Cutwidth of the de Bruijn graph ⋮ Semelectivity is not sufficient ⋮ Area complexity of merging

Cites Work

• The complexity of a VLSI adder
• Area-time tradeoffs for matrix multiplication and related problems in VLSI models
• Information Transfer in Distributed Computing with Applications to VLSI
• The VLSI Complexity of Sorting
• An Architecture for Bitonic Sorting with Optimal VLSI Performnance
• The VLSI Complexity of Selected Graph Problems
• Optimal VLSI circuits for sorting
• The Area-Time Complexity of Binary Multiplication
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Area-time lower-bound techniques with applications to sorting