{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:10Z","timestamp":1787340550842,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,8]]},"abstract":"<jats:p>We study VLSI solutions to the connected component problem on networks that have area too small to store all the edges of the graph for the entire computation. We give lower bounds on the time needed to solve this problem on such networks, as well as an optimal algorithm. The lower bounds use a new proof technique combining adversary strategy, information flow, and Kolmogorov complexity arguments. The lower bounds obtained for the connected components problem hold for a number of other undirected graph problems.<\/jats:p>","DOI":"10.1137\/0214040","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"527-544","source":"Crossref","is-referenced-by-count":5,"title":["Solving Undirected Graph Problems on VLSI"],"prefix":"10.1137","volume":"14","author":[{"given":"Susanne E.","family":"Hambrusch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Janos","family":"Simon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/358808.358814"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. J. Atallah, S. R. Kosaraju,  Graph problems on a mesh-connected processor array,  Proc. 14th Annual ACM Symposium on Theory of Computing,  1982,  345\u2013353","DOI":"10.1145\/800070.802210"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322269"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"B. Chazelle, L. Monier,  A model of computation for VLSI with related complexity results,  Proc. 13th Annual ACM Symposium on Theory of Computing,  1981,  318\u2013325","DOI":"10.1145\/800076.802485"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/360933.360975"},{"key":"R6","unstructured":"L. J. Guibas, H. T. Kung, C. D. Thompson,  Direct VLSI implementations for combinatorial algorithms,  Proc. Conference on VLSI Technology, Design and Fabrication, California Institute of Technology, Pasadena,  1979,  509\u2013525"},{"key":"R7","unstructured":"S. E. Hambrusch, Ph.D. Thesis,  The complexity of graph problems on VLSI, Pennsylvania State Univ., University Park,  1982 0685.68045"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0212023"},{"key":"R9","unstructured":"J. Ja'Ja',  The VLSI complexity of graph problems, Tech. Rep., CS81-25, Pennsylvania State Univ., University Park,  1981, October"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322421"},{"key":"R11","first-page":"260","volume-title":"Introduction to VLSI Systems","author":"Kung H. T.","year":"1980"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"R. J. Lipton, R. S. Sedgewick,  Lower Bounds for VLSI,  Proc. 13th Annual ACM Symposium on Theory of Computing,  1981,  300\u2013307","DOI":"10.1145\/800076.802482"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"R. J. Lipton, J. Valdes,  Census function: An approach to VLSI upper bounds,  Proc. 22nd Annual Symposium on Foundations of Computer Science,  1981,  13\u201322","DOI":"10.1109\/SFCS.1981.13"},{"key":"R14","volume-title":"Introduction to VLSI Systems","author":"Mead C.","year":"1980"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676279"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"W. Paul,  On heads versus tapes,  Proc. 22nd Annual Symposium on Foundations of Computer Science,  1981,  68\u201373","DOI":"10.1109\/SFCS.1981.25"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"W. Paul, J. Seiferas, J. Simon,  An information theoretic approach to time bounds on on-line computation,  Proc.12th Annual ACM Symposium on Theory of Computing,  1980,  357\u2013367","DOI":"10.1145\/800141.804685"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/358645.358660"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"C. Savage,  A systolic data structure chip for connectivity problems,  Proc. CMU Conference on VLSI Systems and Computing,  1981,  296\u2013300","DOI":"10.1007\/978-3-642-68402-9_32"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804401"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676221"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"A. Yao,  Some complexity questions related to distributed computing,  Proc. 11th Annual ACM Symposium on Theory of Computing,  1979,  209\u2013213","DOI":"10.1145\/800135.804414"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214040","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:03Z","timestamp":1787337543000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214040"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,8]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,8]]}},"alternative-id":["10.1137\/0214040"],"URL":"https:\/\/doi.org\/10.1137\/0214040","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,8]]}}}