{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,24]],"date-time":"2026-10-24T00:51:02Z","timestamp":1792803062733,"version":"4.5.0"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1986,11]]},"abstract":"<jats:p>Two basic design strategies are used to develop a very simple and fast parallel algorithms for the maximal independent set (MIS) problem. The first strategy consists of assigning identical copies of a simple algorithm to small local portions of the problem input. The algorithm is designed so that when the copies are executed in parallel the correct problem output is produced very quickly. A very simple Monte Carlo algorithm for the MIS problem is presented which is based upon this strategy. The second strategy is a general and powerful technique for removing randomization from algorithms. This strategy is used to convert the Monte Carlo algorithm for this MIS problem into a simple deterministic algorithm with the same parallel running time.<\/jats:p>","DOI":"10.1137\/0215074","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:28:10Z","timestamp":1109226490000},"page":"1036-1053","source":"Crossref","is-referenced-by-count":781,"title":["A Simple Parallel Algorithm for the Maximal Independent Set Problem"],"prefix":"10.1137","volume":"15","author":[{"given":"Michael","family":"Luby","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","unstructured":"N. lon, private communication"},{"key":"R2","unstructured":"R. Anderson, private communication"},{"key":"R3","unstructured":"B. Alexi, B. Chor, O. Goldreich, C. Schnorr,  RSA\/ Rabin bits are  $\\frac{1}{2}+1\/\\mathrm{poly}(\\log N)$ secure, Preliminary version,  1984, Proc. 25th IEEE Symposium on Foundations of Computer Science, October this Journal, to appear"},{"key":"R4","unstructured":"N. Alon, L. Babai, A. Itai,  A fast and simple randomized parallel algorithm for the maximal independent set problem, private communication"},{"key":"R5","unstructured":"P. Beame, private communication"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002168X"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1952-0045327-5"},{"key":"R8","unstructured":"B. Chor, G. Friedman, O. Goldreich, J. Hastaad, S. Rudich, R. Smolanski,  The bit extraction problem, preprint, accepted to Proc. 26th IEEE Symposium on Foundations of Computer Science"},{"key":"R9","unstructured":"B. Chor, O. Goldreich,  On the power of two-points based sampling, technical report, MIT Laboratory for Computer Science, Cambridge, MA"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"R11","unstructured":"S. Cook, M. Luby,  A fast parallel algorithm for finding a truth assignment to a  2-CNF formula, in preparation"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"R13","volume-title":"Parallel Models of Associative Memory","author":"Feldman J. A.","year":"1981"},{"key":"R14","volume-title":"An introduction to probability theory and its applications. Vol. I","author":"Feller William","year":"1968"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804339"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176995765"},{"key":"R17","unstructured":"L. M. Goldschlager,  A computational theory of higher brain function, Technical Report, Stanford Univ., Stanford, CA,  1984, April"},{"key":"R18","volume-title":"Combinatorial theory","author":"Hall, Jr. Marshall","year":"1967"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.79.8.2554"},{"key":"R20","unstructured":"G. E. Hinton, T. Sejnowski, D. Ackley,  Boltzmann machines: constraint satisfaction networks that learn, Technical Report, CMU-CS-84-119, Carnegie-Mellon Univ., Pittsburgh, PA"},{"key":"R21","unstructured":"A. Israeli, A. Itai,  A fast and simple randomized parallel algorithm for maximal matching, Computer Science Dept., Technion, Haifa, Israel,  1984"},{"key":"R22","unstructured":"A. Israeli, Y. Shiloach,  An improved maximal matching parallel algorithm, Technical Report, 333, Computer Science Dept., Technion, Haifa, Israel,  1984"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1971-0279857-5"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996762"},{"key":"R25","unstructured":"H. Karloff,  Randomized parallel algorithm for the odd-set cover problem, preprint"},{"key":"R26","unstructured":"H. Karloff, private communication"},{"key":"R27","unstructured":"R. Karp, N. Pippenger,  A time-randomness tradeoff,  presented at the AMS Conference on Probabilistic Computational Complexity, Durham, NH,  1982"},{"key":"R28","unstructured":"H. Karloff, D. Shmoys, D. Soroker,  Efficient parallel algorithms for graph coloring and partitioning problems, preprint"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"R. M. Karp, A. Wigderson,  A fast parallel algorithm for the maximal independent set problem,  Proc. 16th ACM Symposium on Theory of Computing,  1984,  266\u2013272","DOI":"10.1145\/800057.808690"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"R. M. Karp, E. Upfal, A. Wigderson,  Constructing a perfect matching is in random NC,  Proc. 17th ACM Symposium on Theory of Computing,  1985,  22\u201332","DOI":"10.1145\/22145.22148"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177700007"},{"key":"R32","unstructured":"G. Lev,  Size bounds and parallel algorithms for networks, Report, CST-8-80, Dept. Computer Science, Univ. Edinburgh,  1980"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"M. Luby,  A simple parallel algorithm for the maximal independent set problem,  Proc.17th ACM Symposium on Theory of Computing,  1985,  1\u201310","DOI":"10.1145\/22145.22146"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176994834"},{"key":"R35","volume-title":"Probability theory","author":"R\u00e9nyi A.","year":"1970"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"M. Sipser,  A complexity theoretic approach to randomness,  Proc. 15th ACM Symposium on Theory of Computing,  1983,  330\u2013335","DOI":"10.1145\/800061.808762"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"L. Stockmeyer,  The complexity of approximate counting,  Proc. 15th ACM Symposium on Theory of Computing,  1983,  118\u2013126","DOI":"10.1145\/800061.808740"},{"key":"R39","unstructured":"J. Tsotsos,  Representational axes and temporal cooperative processes, Technical Report, RBCV-84-2, Univ. Toronto, Toronto, Ontario,  1984, April"},{"key":"R40","unstructured":"L. G. Valiant,  Parallel computation,  Proc. 7th IBM Symposium on Mathematical Foundations of Computer Science,  1982"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0215074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:09Z","timestamp":1787337729000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0215074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,11]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1986,11]]}},"alternative-id":["10.1137\/0215074"],"URL":"https:\/\/doi.org\/10.1137\/0215074","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,11]]}}}