{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:55Z","timestamp":1742617195724,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540580782"},{"type":"electronic","value":"9783540484356"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58078-6_3","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:10:59Z","timestamp":1330269059000},"page":"23-34","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The parallel complexity of algorithms for pattern formation models"],"prefix":"10.1007","author":[{"given":"Raymond","family":"Greenlaw","sequence":"first","affiliation":[]},{"given":"Jonathan","family":"Machta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"issue":"3","key":"3_CR1","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1209\/0295-5075\/17\/3\/001","volume":"17","author":"A. Apostolakis","year":"1992","unstructured":"A. Apostolakis, P. Coddington, and E. Marinari. A multi-grid cluster labeling scheme. Europhysics Letters, 17(3):189\u2013194, 1992.","journal-title":"Europhysics Letters"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"G. Barnes, J.F. Buss, W.L. Ruzzo, and B. Schieber. A sublinear space, polynomial time algorithm for directed s \u2014 t connectivity. In Proceedings of the 7th Annual Structure in Complexity Theory Conference, pages 27\u201333, 1992.","DOI":"10.1109\/SCT.1992.215378"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"G. Barnes and W.L. Ruzzo. Deterministic algorithms for undirected s \u2014 t connectivity using polynomial time and sublinear space. In Proceedings of the 23rd ACM Symposium on the Theory of Computing, pages 43\u201353, 1991.","DOI":"10.1145\/103418.103430"},{"key":"3_CR4","unstructured":"C. H. Bennett. How to define complexity in physics, and why. In W. H. Zurek, editor, Complexity, Entropy and the Physics of Information, pages 137\u2013148. Addison-Wesley, 1990."},{"issue":"1\/2","key":"3_CR5","first-page":"73","volume":"63","author":"R.C. Brower","year":"1992","unstructured":"R.C. Brower, P. Tamayo, and B. York. A parallel multi-grid algorithm for percolation clusters. Journal of Statistical Physics, 63(1\/2):73\u201388, 1992.","journal-title":"Journal of Statistical Physics"},{"issue":"8","key":"3_CR6","doi-asserted-by":"crossref","first-page":"4106","DOI":"10.1103\/PhysRevA.38.4106","volume":"38","author":"D.Y.C. Chan","year":"1988","unstructured":"D.Y.C. Chan, B.D. Hughes, L. Paterson, and C. Sirakoff. Simulating flow in porous media. Physical Review A, 38(8):4106\u20134120, 1988.","journal-title":"Physical Review A"},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1017\/S0022112082001335","volume":"119","author":"R. Chandler","year":"1982","unstructured":"R. Chandler, J. Koplick, K. Lerman, and J. F. Willemsen. Capillary displacement and percolation in porous media. Journal of Fluid Mechanics, 119:249\u2013267, 1982.","journal-title":"Journal of Fluid Mechanics"},{"issue":"2","key":"3_CR8","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"L. M. Goldschlager","year":"1977","unstructured":"L. M. Goldschlager. The monotone and planar circuit value problems are log space complete for P. SIGACT News, 9(2):25\u201329, 1977.","journal-title":"SIGACT News"},{"key":"3_CR9","unstructured":"R. Greenlaw. Breadth-Depth search is P-complete. Parallel Processing Letters, 3(3). To appear."},{"issue":"2","key":"3_CR10","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0890-5401(92)90033-C","volume":"97","author":"R. Greenlaw","year":"1992","unstructured":"R. Greenlaw. A model classifying algorithms as inherently sequential with applications to graph searching. Information and Computation, 97(2):133\u2013149, 1992.","journal-title":"Information and Computation"},{"key":"3_CR11","unstructured":"R. Greenlaw, H.J. Hoover, and W.L. Ruzzo. Topics in Parallel Computation: A Guide to P-completeness Theory. Computing Science Series, editor Z. Galil. Oxford University Press. To appear."},{"key":"3_CR12","unstructured":"R. Greenlaw and J. Machta. On the parallel complexity of invasion percolation. Technical Report 93-04, University of New Hampshire, 1993."},{"key":"3_CR13","volume-title":"Fundamentals of Computer Algorithms","author":"E. Horowitz","year":"1984","unstructured":"E. Horowitz and S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press, Rockville, Md., 1984."},{"issue":"20","key":"3_CR14","doi-asserted-by":"crossref","first-page":"4895","DOI":"10.1088\/0305-4470\/24\/20\/021","volume":"24","author":"Z. Koza","year":"1991","unstructured":"Z. Koza. The equivalence of the DLA and a hydrodynamic model. Journal of Physics A: Mathematical and General, 24(20):4895\u20134905, 1991.","journal-title":"Journal of Physics A: Mathematical and General"},{"issue":"3\/4","key":"3_CR15","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1007\/BF01053602","volume":"70","author":"J. Machta","year":"1993","unstructured":"J. Machta. The computational complexity of pattern formation. Journal of Statistical Physics, 70(3\/4):949\u2013966, 1993.","journal-title":"Journal of Statistical Physics"},{"key":"3_CR16","unstructured":"J. Machta and R. Greenlaw. The parallel complexity of growth models. Technical Report 94-05, University of New Hampshire, 1994."},{"issue":"5","key":"3_CR17","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"J. Reif","year":"1985","unstructured":"J. Reif. Depth-first search is inherently sequential. Information Processing Letters, 20(5):229\u2013234, 1985.","journal-title":"Information Processing Letters"},{"key":"3_CR18","doi-asserted-by":"crossref","DOI":"10.1142\/0511","volume-title":"Fractal Growth Phenomena","author":"T. Vicsek","year":"1989","unstructured":"T. Vicsek. Fractal Growth Phenomena. World Scientific, Singapore, 1989."},{"issue":"14","key":"3_CR19","doi-asserted-by":"crossref","first-page":"3365","DOI":"10.1088\/0305-4470\/16\/14\/028","volume":"16","author":"D. Wilkinson","year":"1983","unstructured":"D. Wilkinson and J. F. Willemsen. Invasion percolation: A new form of percolation theory. Journal of Physics A: Mathematical and General, 16(14):3365\u20133376, 1983.","journal-title":"Journal of Physics A: Mathematical and General"},{"issue":"19","key":"3_CR20","doi-asserted-by":"crossref","first-page":"1400","DOI":"10.1103\/PhysRevLett.47.1400","volume":"47","author":"T. A. Witten","year":"1981","unstructured":"T. A. Witten and L. M. Sander. Diffusion-limited aggregation, a kinetic critical phenomenon. Physical Review Letters, 47(19):1400\u20131403, 1981.","journal-title":"Physical Review Letters"}],"container-title":["Lecture Notes in Computer Science","Parallel and Distributed Computing Theory and Practice"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58078-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:18:51Z","timestamp":1742595531000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58078-6_3"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540580782","9783540484356"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-58078-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}