{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T21:30:40Z","timestamp":1673299840988},"reference-count":23,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1990,11,1]],"date-time":"1990-11-01T00:00:00Z","timestamp":657417600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8294,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1990,11]]},"DOI":"10.1016\/0166-218x(90)90082-n","type":"journal-article","created":{"date-parts":[[2002,10,11]],"date-time":"2002-10-11T12:43:22Z","timestamp":1034340202000},"page":"63-78","source":"Crossref","is-referenced-by-count":8,"title":["Incomparability in parallel computation"],"prefix":"10.1016","volume":"29","author":[{"given":"Vince","family":"Grolmusz","sequence":"first","affiliation":[]},{"given":"Prabhakar","family":"Ragde","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0166-218X(90)90082-N_BIB1","article-title":"Optimal bounds for decision problems on the CRCW PRAM","author":"Beame","year":"1987","journal-title":"Proceedings 19th ACM Symposium on Theory of Computing"},{"key":"10.1016\/0166-218X(90)90082-N_BIB2","series-title":"Graphs and Hypergraphs","author":"Berge","year":"1973"},{"key":"10.1016\/0166-218X(90)90082-N_BIB3","first-page":"1","article-title":"A complexity theory of unbounded fan-in parallelism","author":"Chandra","year":"1982","journal-title":"Proceedings 23rd Annual IEEE Symposium on Foundations of Computer Science"},{"key":"10.1016\/0166-218X(90)90082-N_BIB4","first-page":"478","article-title":"Approximate and exact parallel scheduling with applications to list, tree, and graph problems","author":"Cole","year":"1986","journal-title":"Proceedings 27th Annual IEEE Symposium on Foundations of Computer Science"},{"issue":"1","key":"10.1016\/0166-218X(90)90082-N_BIB5","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/0215006","article-title":"Upper and lower bounds for parallel random access machines without simultaneous writes","volume":"15","author":"Cook","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(90)90082-N_BIB6","first-page":"85","article-title":"Intersection theorems for systems of sets","volume":"35","author":"Erdőos","year":"1960","journal-title":"J. London Math. Soc."},{"key":"10.1016\/0166-218X(90)90082-N_BIB7","article-title":"Lower bounds for parallel random-access machines with unbounded shared memory","author":"Fich","year":"1986","journal-title":"Advances in Computing Research"},{"key":"10.1016\/0166-218X(90)90082-N_BIB8","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/800222.806745","article-title":"Relations between concurrent-write models of parallel computation (preliminary version)","author":"Fich","year":"1984","journal-title":"Proceedings 3rd Annual ACM Symposium on Principles of Distributed Computing"},{"key":"10.1016\/0166-218X(90)90082-N_BIB9","author":"Fich","year":"1986","journal-title":"Simulations among concurrent-write PRAMs"},{"key":"10.1016\/0166-218X(90)90082-N_BIB10","author":"Fich","year":"1987","journal-title":"Relations between concurrent-write models of parallel computation"},{"key":"10.1016\/0166-218X(90)90082-N_BIB11","first-page":"240","article-title":"Optimal parallel algorithms for string matching","author":"Galil","year":"1984","journal-title":"Proceedings 16th Annual ACM Symposium on Theory of Computing"},{"key":"10.1016\/0166-218X(90)90082-N_BIB12","first-page":"492","article-title":"An optimal randomized algorithm for finding connected components in graphs","author":"Gazit","year":"1986","journal-title":"Proceedings 27th Annual IEEE Symposium on Foundations of Computer Science"},{"issue":"4","key":"10.1016\/0166-218X(90)90082-N_BIB13","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","article-title":"A unified approach to models of synchronous parallel machines","volume":"29","author":"Goldschlager","year":"1982","journal-title":"J. ACM"},{"key":"10.1016\/0166-218X(90)90082-N_BIB14","series-title":"Ph.D. Thesis","article-title":"Efficient algorithms for multiple access channels","author":"Greenberg","year":"1983"},{"issue":"2","key":"10.1016\/0166-218X(90)90082-N_BIB15","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0020-0190(82)90093-X","article-title":"Parallel computation and conflicts in memory access","volume":"14","author":"Ku\u010dera","year":"1982","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0166-218X(90)90082-N_BIB16","first-page":"177","article-title":"New lower bounds for parallel computation","author":"Li","year":"1986","journal-title":"Proceedings 18th Annual ACM Symposium on Theory of Computing"},{"key":"10.1016\/0166-218X(90)90082-N_BIB17","author":"Ragde","year":"1986","journal-title":"The parallel complexity of element distinctness is \u03a9(log n"},{"key":"10.1016\/0166-218X(90)90082-N_BIB18","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1112\/plms\/s2-30.1.264","article-title":"On a problem of formal logic","volume":"30","author":"Ramsey","year":"1930","journal-title":"Proc. London Math. Soc. Ser. 2"},{"key":"10.1016\/0166-218X(90)90082-N_BIB19","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","article-title":"Finding the maximum, merging, and sorting on parallel models of computation","volume":"2","author":"Shiloach","year":"1981","journal-title":"J. Algorithms"},{"key":"10.1016\/0166-218X(90)90082-N_BIB20","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","article-title":"An O(log n) parallel connectivity algorithm","volume":"3","author":"Shiloach","year":"1982","journal-title":"J. Algorithms"},{"issue":"2","key":"10.1016\/0166-218X(90)90082-N_BIB21","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1137\/0214051","article-title":"On parallel searching","volume":"14","author":"Snir","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(90)90082-N_BIB22","first-page":"12","article-title":"Finding biconnected components and computing tree functions in logarithmic parallel time","author":"Tarjan","year":"1984","journal-title":"Proceedings 25th Annual ACM Symposium on Foundations of Computer Science"},{"key":"10.1016\/0166-218X(90)90082-N_BIB23","series-title":"Tech. Rept. 210","article-title":"Implementation of simultaneous memory address access in models that forbid it","author":"Vishkin","year":"1981"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X9090082N?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X9090082N?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T06:51:15Z","timestamp":1554965475000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0166218X9090082N"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,11]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1990,11]]}},"alternative-id":["0166218X9090082N"],"URL":"https:\/\/doi.org\/10.1016\/0166-218x(90)90082-n","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1990,11]]}}}