{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T05:20:50Z","timestamp":1735881650550,"version":"3.32.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1986,11,1]],"date-time":"1986-11-01T00:00:00Z","timestamp":531187200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1986,11]]},"DOI":"10.1007\/bf01840437","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T21:29:13Z","timestamp":1121290153000},"page":"65-91","source":"Crossref","is-referenced-by-count":25,"title":["Area-time lower-bound techniques with applications to sorting"],"prefix":"10.1007","volume":"1","author":[{"given":"G.","family":"Bilardi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F. P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01840437_CR1","unstructured":"C. D. Thompson,A Complexity Theory for VLSI, Ph.D. Thesis, Dept. of Comp. Science, Carnegie-Mellon University; August 1980."},{"issue":"n. 2","key":"BF01840437_CR2","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0020-0190(80)90010-1","volume":"11","author":"R. B. Johnson","year":"1980","unstructured":"R. B. Johnson, \u201cThe complexity of a VLSI adder,\u201dInformation Processing Letters, vol. 11, n. 2, pp. 92\u201393; October 1980.","journal-title":"Information Processing Letters"},{"key":"BF01840437_CR3","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/978-3-642-68402-9_12","volume-title":"VLSI Systems and Computations","author":"G. M. Baudet","year":"1981","unstructured":"G. M. Baudet, \u201cOn the area required by VLSI circuits,\u201d in H. T. Kung, R. Sproull, and G. Steele (eds.),VLSI Systems and Computations, pp. 100\u2013107, Computer Science Press, Rockville, MD; 1981."},{"key":"BF01840437_CR4","doi-asserted-by":"crossref","unstructured":"Z. Kedem, \u201cOptimal allocation of computational resources in VLSI,\u201dProc. 23rd Annual Symposium on the Foundations of Computer Science, Chicago, IL, pp. 379\u2013386; November 1982.","DOI":"10.1109\/SFCS.1982.32"},{"key":"BF01840437_CR5","volume-title":"Proceedings 1984 Conference on Advanced Research in VLSI","author":"A. Gamal El","year":"1984","unstructured":"A. El Gamal, J. W. Greene, and K. F. Pang, \u201cVLSI complexity of coding,\u201dProceedings 1984 Conference on Advanced Research in VLSI, M.I.T., Cambridge, MA; January 1984."},{"key":"BF01840437_CR6","unstructured":"D. Angluin, \u201cVLSI; On the merits of batching,\u201dmanuscript; April 1982."},{"key":"BF01840437_CR7","doi-asserted-by":"crossref","unstructured":"A. Siegel, \u201cMinimal storage sorting circuits,\u201dIEEE Trans, on Comput., vol. C-34, n. 4; April 1985.","DOI":"10.1109\/TC.1985.5009386"},{"key":"BF01840437_CR8","unstructured":"S. E. Hambrush and J. Simon, \u201cSolving undirected graph problems on VLSI,\u201dCS-81-23,Computer Science Department, Pennsylvania State Univ., Univ. Park, PA, December 1981."},{"issue":"No. 2","key":"BF01840437_CR9","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1145\/62.70","volume":"31","author":"J. Ja'Ja'","year":"1984","unstructured":"J. Ja'Ja', \u201cThe VLSI complexity of selected graph problems,\u201dJournal of the ACM, Vol. 31, No. 2, pp. 377\u2013391; April 1984.","journal-title":"Journal of the ACM"},{"key":"BF01840437_CR10","doi-asserted-by":"crossref","unstructured":"A. C. C. Yao, \u201cSome complexity questions related to distributive computing,\u201dProc. 11th Annual ACM Symposium on Theory of Computing, Atlanta, GA, pp. 209\u2013213; April 1979.","DOI":"10.1145\/800135.804414"},{"key":"BF01840437_CR11","doi-asserted-by":"crossref","unstructured":"A. C. C. Yao, \u201cThe entropie limitations on VLSI computations,\u201dProc. 13th Annual ACM Symposium on Theory of Computing, Milwaukee, WI, pp. 308\u2013311; April 1981.","DOI":"10.1145\/800076.802483"},{"issue":"n. 1","key":"BF01840437_CR12","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1145\/2422.322421","volume":"31","author":"J. Ja'Ja'","year":"1984","unstructured":"J. Ja'Ja' and V. K. P. Kumar, \u201cInformation transfer in distributed computing with applications to VLSI,Journal of the ACM, vol. 31, n. 1, pp. 150\u2013162; January 1984.","journal-title":"Journal of the ACM"},{"issue":"n. 2","key":"BF01840437_CR13","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/0022-0000(81)90029-5","volume":"22","author":"J. E. Savage","year":"1981","unstructured":"J. E. Savage, \u201cArea-time tradeoffs for matrix multiplication and related problems in VLSI models,\u201dJournal of Computer System Science, vol. 22, n. 2, pp. 230\u2013242; April 1981.","journal-title":"Journal of Computer System Science"},{"issue":"n. 3","key":"BF01840437_CR14","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1145\/322261.322269","volume":"28","author":"R. P. Brent","year":"1981","unstructured":"R. P. Brent and H. T. Kung, \u201cThe chip complexity of binary arithmetic,\u201dJournal of the ACM, vol. 28, n. 3, pp. 521\u2013534; My 1981.","journal-title":"Journal of the ACM"},{"key":"BF01840437_CR15","doi-asserted-by":"crossref","unstructured":"F. T. Leighton, \u201cTight bounds on the complexity of parallel sorting,\u201dProc. 16th Annual ACM Symposium on Theory of Computing, Washington, D.C., pp. 71\u201380; April 1984. (AlsoIEEE Trans. on Comput.; April 1985.)","DOI":"10.1109\/TC.1985.5009385"},{"key":"BF01840437_CR16","unstructured":"P. Duris, O. Sykora, C. Thompson, and I. Vrto, \u201cA tight chip area lower bound for sorting,\u201dComputers and Artificial Intelligence, to appear; 1985."},{"key":"BF01840437_CR17","volume-title":"Computational Aspects of VLSI","author":"J. D. Ullman","year":"1983","unstructured":"J. D. Ullman,Computational Aspects of VLSI, Computer Science Press, Rockville, MD, 1983."},{"key":"BF01840437_CR18","unstructured":"C. D. Thompson and D. Angluin, \u201cOnAT 2 lower bounds for sorting,\u201dmanuscript draff; March 1983."},{"key":"BF01840437_CR19","unstructured":"A. Siegel, \u201cTight area bounds and provably goodAT 2 bounds for sorting circuits,\u201d Tech. Report #122 Courant Institute, New York University; June 1984."},{"key":"BF01840437_CR20","unstructured":"G. Bilardi,The Area-Time Complexity of Sorting, Ph.D. Thesis, Univ. of Illinois; December 1984."},{"issue":"n. 7","key":"BF01840437_CR21","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1109\/TC.1984.5009338","volume":"C-33","author":"G. Bilardi","year":"1984","unstructured":"G. Bilardi and F. P. Preparata, \u201cAn architecture for bitonic sorting with optimal VLSI performance,\u201dIEEE Trans. Comp., vol. C-33, n. 7, pp. 640\u2013651; July 1984.","journal-title":"IEEE Trans. Comp."},{"key":"BF01840437_CR22","doi-asserted-by":"crossref","unstructured":"G. Bilardi and F. P. Preparata, \u201cA minimum area VLSI network forO(logN) time sorting,\u201dProc. 16th Annual ACM Symposium on Theory of Computing, Washington, D.C., pp. 64\u201370; April 1984. (AlsoIEEE Trans. on Comput., April 1985.)","DOI":"10.1145\/800057.808666"},{"issue":"n. 2","key":"BF01840437_CR23","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0020-0190(85)90062-6","volume":"20","author":"G. Bilardi","year":"1985","unstructured":"G. Bilardi and F. P. Preparata, \u201cThe VLSI optimality of the AKS sorting network,\u201dInformation Processing Letters, vol. 20, n. 2, pp. 55\u201359, Feb. 1985.","journal-title":"Information Processing Letters"},{"key":"BF01840437_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0015730","volume-title":"The influence of key length on the area-time complexity of sorting","author":"G. Bilardi","year":"1985","unstructured":"G. Bilardi and F. P. Preparata, \u201cThe influence of key length on the area-time complexity of sorting,\u201d I. C. A. L. P., Nauplion, Greece; July 1985."},{"key":"BF01840437_CR25","unstructured":"R. Cole and A. Siegel, \u201cOptimal VLSI circuits for sorting,\u201d manuscript; 1985."},{"issue":"n. 12","key":"BF01840437_CR26","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1109\/TC.1983.1676178","volume":"C-32","author":"C. D. Thompson","year":"1983","unstructured":"C. D. Thompson, \u201cThe VLSI complexity of sorting,\u201dIEEE Trans. Comp., vol. C-32, n. 12, pp. 1171\u20131184; December 1983.","journal-title":"IEEE Trans. Comp."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840437.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840437\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840437","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T13:46:08Z","timestamp":1735825568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840437"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,11]]},"references-count":26,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1986,11]]}},"alternative-id":["BF01840437"],"URL":"https:\/\/doi.org\/10.1007\/bf01840437","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1986,11]]}}}