Area-time lower-bound techniques with applications to sorting

DOI10.1007/BF01840437MaRDI QIDQ1091139zbMATH OpenFDO

Authors Gianfranco Bilardi, F. P. Preparata

Publication date 1986

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

lower boundssortinginformation exchangearea-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)

Recommendations

• scientific article; zbMATH DE number 3940717
• scientific article; zbMATH DE number 3915623
• scientific article; zbMATH DE number 3911723
• A Minimum Area VLSI Network for O(log n) Time Sorting
• scientific article; zbMATH DE number 3894473

Cites work

• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 3911723 (Why is no real title available?)
• scientific article; zbMATH DE number 3940717 (Why is no real title available?)
• An Architecture for Bitonic Sorting with Optimal VLSI Performnance
• Area-time tradeoffs for matrix multiplication and related problems in VLSI models
• Information Transfer in Distributed Computing with Applications to VLSI
• Optimal VLSI circuits for sorting
• The Area-Time Complexity of Binary Multiplication
• The VLSI Complexity of Selected Graph Problems
• The VLSI Complexity of Sorting
• The complexity of a VLSI adder

Cited in

(21)

• Minimum Storage Sorting Networks
• Optimal tradeoffs for addition on systolic arrays
• scientific article; zbMATH DE number 3911723 (Why is no real title available?)
• scientific article; zbMATH DE number 4026821 (Why is no real title available?)
• scientific article; zbMATH DE number 3894473 (Why is no real title available?)
• Cutwidth of the de Bruijn graph
• scientific article; zbMATH DE number 3915623 (Why is no real title available?)
• scientific article; zbMATH DE number 3940717 (Why is no real title available?)
• Semelectivity is not sufficient
• VLSI-sorting evaluated under the linear model
• The area-time complexity of the greatest common divisor problem: A lower bound
• Theoretical Aspects of VLSI Pin Limitations
• On the expansion and diameter of bluetooth-like topologies
• Area complexity of merging
• On problem transformability in VLSI
• scientific article; zbMATH DE number 5182609 (Why is no real title available?)
• The area-time complexity of the VLSI counter
• On the VLSI complexity of some arithmetic and numerical problems
• Lower bounds to processor-time tradeoffs under bounded-speed message propagation
• Upper bounds for time-space trade-offs in sorting and selection
• scientific article; zbMATH DE number 1263218 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1091139)