{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:12:29Z","timestamp":1725459149765},"publisher-location":"Berlin\/Heidelberg","reference-count":22,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540123172"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0036916","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T12:38:14Z","timestamp":1138192694000},"page":"292-303","source":"Crossref","is-referenced-by-count":1,"title":["Lower bounds for solving undirected graph problems on VLSI"],"prefix":"10.1007","author":[{"given":"Susanne E.","family":"Hambrusch","sequence":"first","affiliation":[]},{"given":"Janos","family":"Simon","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/358808.358814","volume":"23","author":"H. Abelson","year":"1980","unstructured":"H. Abelson, P. Andreae, \u2018Information Transfer and Area-Time Tradeoffs for VLSI Multiplication', CACM, Vol. 23, pp 20\u201323, Jan. 1980.","journal-title":"CACM"},{"doi-asserted-by":"crossref","unstructured":"M.J. Atallah, S.R. Kosaraju, \u2018Graph Problems on a Mesh-Connected Processor Array', Proc. of the 14-th Ann. Symp. on Th. of Comp., pp 345\u2013353, 1982.","key":"24_CR2","DOI":"10.1145\/800070.802210"},{"key":"24_CR3","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1145\/322261.322269","volume":"28","author":"R.P. Brent","year":"1981","unstructured":"R.P. Brent, H.T. Kung, \u2018The Area-Time Complexity of Binary Multiplication', JACM, Vol.28, pp 521\u2013534, July 1981.","journal-title":"JACM"},{"doi-asserted-by":"crossref","unstructured":"B. Chazelle, L. Monier, \u2018A Model of Computation for VLSI with Related Complexity Results', 13-th Ann. Symp. on Th. of Comp., pp 318\u2013325, 1981.","key":"24_CR4","DOI":"10.1145\/800076.802485"},{"unstructured":"G.N. Frederickson, D.B. Johnson, \u2018Generalized Selection and Ranking: Sorted Matrices', Tech. Report of The Pennsylvania State University, CS-81-12, 1981.","key":"24_CR5"},{"unstructured":"L.J. Guibas, H.T. Kung, CD. Thompson, \u2018Direct VLSI Implementations for Combinatorial Algorithms', Proc. of Conf. VLSI Tech. Design and Fabrication, Caltech 1979.","key":"24_CR6"},{"unstructured":"S.E. Hambrusch, \u2018The Complexity of Graph Problems on VLSI', Ph.D. thesis, The Pennsylvania State University, 1982.","key":"24_CR7"},{"doi-asserted-by":"crossref","unstructured":"S.E. Hambrusch, \u2018VLSI Algorithms for the Connected Components Problem', SIAM J. on Computing, Vol. 12, No. 2, May 1983.","key":"24_CR8","DOI":"10.1137\/0212023"},{"unstructured":"J. Ja'sJa', \u2018The VLSI Complexity of Graph Problems', Tech. Report of The Pennsylvania State University, CS-81-25, October 1981.","key":"24_CR9"},{"unstructured":"J. Ja'sJa', V.K. Kumar, \u2018Information Transfer in Distributed Computing with Applications to VLSI', Tech. Report of The Pennsylvania State University, CS-81-14, 1981.","key":"24_CR10"},{"unstructured":"H.T. Kung, C.E. Leiserson, 'systolic Arrays for VLSI', appeared in Introduction to VLSI Systems', C. Mead, L. Conway, Addison-Wesley, pp 260\u2013292, 1960.","key":"24_CR11"},{"doi-asserted-by":"crossref","unstructured":"R.J. Lipton, R.S. Sedgewick, \u2018Lower Bounds for VLSI', 13-th Ann. Symp. on Th. of Comp., pp 300\u2013307, 1981.","key":"24_CR12","DOI":"10.1145\/800076.802482"},{"doi-asserted-by":"crossref","unstructured":"R.J. Lipton, J. Valdes, \u2018Census Function: An Approach to VLSI Upper Bounds', Proc. of the 22-nd Ann. Symp. on Found. of Comp. Sc, pp 13\u201322, 1981.","key":"24_CR13","DOI":"10.1109\/SFCS.1981.13"},{"unstructured":"C. Mead, L. Conway, Introduction to VLSI Systems, Addison-Wesley, 1980.","key":"24_CR14"},{"unstructured":"D. Nath, S.N. Maheshwari, P.C.P. Bhatt, \u2018Efficient VLSI Networks for Parallel Processing based on Orthogonal Trees', Techn. Report of the Indian Inst. of Techn., Delhi, April 1981.","key":"24_CR15"},{"doi-asserted-by":"crossref","unstructured":"W. Paul, \u2018On Heads versus Tapes', 22-nd Ann. Symp. on Found, of Comp. Sc., pp 68\u201373, 1981.","key":"24_CR16","DOI":"10.1109\/SFCS.1981.25"},{"doi-asserted-by":"crossref","unstructured":"W. Paul, J. Seiferas, J. Simon, \u2018An Information Theoretic Approach to Time Bounds on On-line Computation', 12-th Ann. Symp. on Th. of Comp., pp 357\u2013367, 1980.","key":"24_CR17","DOI":"10.1145\/800141.804685"},{"doi-asserted-by":"crossref","unstructured":"F.P. Preparata, J.E. Vuillemin, \u2018The Cube Connected Cycles: a Versatile Network for Parallel Computation', Proc. of 20-th annual IEEE FOCS Conf., pp 140\u2013147, 1979.","key":"24_CR18","DOI":"10.1109\/SFCS.1979.43"},{"doi-asserted-by":"crossref","unstructured":"L. Snyder, \u2018Overview of the CHiP Computer', in John P. Gray, VLSI 1981, pp 237\u2013246, Academic Press, 1981.","key":"24_CR19","DOI":"10.21236\/ADA109293"},{"doi-asserted-by":"crossref","unstructured":"C.D. Thompson, \u2018Area-Time Complexity for VLSI', 11-th Ann. Symp, on Th. of Comp., pp B1\u201388, 1979.","key":"24_CR20","DOI":"10.1145\/800135.804401"},{"doi-asserted-by":"crossref","unstructured":"J.E. Vuillemin, \u2018A Combinatorial Limit to the Computing Power of VLSI Circuits', 21-st Ann. Symp. on Found. of Comp. Sc., pp 294\u2013300, 1980.","key":"24_CR21","DOI":"10.1109\/TC.1983.1676221"},{"doi-asserted-by":"crossref","unstructured":"A. Yao, 'some Complexity Questions related to Distributed Computing', Proc. 11-th Ann. Symp. on Th. of Comp., pp 209\u2013213, 1979.","key":"24_CR22","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0036916.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T17:21:34Z","timestamp":1607534494000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0036916"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540123172"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/bfb0036916","relation":{},"subject":[]}}