{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:20:47Z","timestamp":1725456047962},"publisher-location":"Berlin\/Heidelberg","reference-count":17,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540543430"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028260","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T00:52:14Z","timestamp":1132620734000},"page":"177-188","source":"Crossref","is-referenced-by-count":0,"title":["A fast derandomization scheme and its applications"],"prefix":"10.1007","author":[{"given":"Yijie","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"N. Alon, L. Babai, A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. of Algorithms 7, 567\u2013583(1986).","journal-title":"J. of Algorithms"},{"key":"17_CR2","unstructured":"B. Berger, J. Rompel. Simulating (logc n)-wise independence in NC. Proc. 1989 IEEE FOCS, 2\u20137."},{"key":"17_CR3","unstructured":"B. Berger, J. Rompel, P. Shor. Efficient NC algorithms for set cover with applications to learning and geometry. Proc. 1989 IEEE FOCS, 54\u201359."},{"issue":"3","key":"17_CR4","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1137\/0402028","volume":"2","author":"M. Goldberg","year":"1989","unstructured":"M. Goldberg, T. Spencer. Constructing a maximal independent set in parallel. SIAM J. Dis. Math., Vol 2, No. 3, 322\u2013328(Aug. 1989).","journal-title":"SIAM J. Dis. Math."},{"key":"17_CR5","unstructured":"Y. Han. A parallel algorithm for the PROFIT\/COST problem. To appear in Proc. of 1991 Int. Conf. on Parallel Processing, (AUg. 1991)."},{"key":"17_CR6","unstructured":"Y. Han. A fast derandomization scheme and its applications. Tech. Report, TR No. 180\u201390, Computer Science Dept., University of Kentucky, Lexington, Kentucky."},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Y. Han and Y. Igarashi. Derandomization by exploiting redundancy and mutual independence. Proc. SIGAL 1990, LNCS 450, 328\u2013337.","DOI":"10.1007\/3-540-52921-7_82"},{"key":"17_CR8","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0020-0190(86)90141-9","volume":"22","author":"A. Israeli","year":"1986","unstructured":"A. Israeli, Y. Shiloach. An improved parallel algorithm for maximal matching. Information Processing Letters 22(1986), 57\u201360.","journal-title":"Information Processing Letters"},{"issue":"4","key":"17_CR9","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"R. Karp","year":"1985","unstructured":"R. Karp, A. Wigderson. A fast parallel algorithm for the maximal independent set problem. JACM 32:4, Oct. 1985, 762\u2013773.","journal-title":"JACM"},{"issue":"4","key":"17_CR10","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15:4, Nov. 1986, 1036\u20131053.","journal-title":"SIAM J. Comput."},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"M. Luby. Removing randomness in parallel computation without a processor penalty. Proc. 1988 IEEE FOCS, 162\u2013173.","DOI":"10.1109\/SFCS.1988.21934"},{"key":"17_CR12","unstructured":"M. Luby. Removing randomness in parallel computation without a processor penalty. TR-89-044, Int. Comp. Sci. Institute, Berkeley, California."},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif. Parallel tree contraction and its application. Proc. 26th Symp. on Foundations of Computer Science, IEEE, 291\u2013298(1985).","DOI":"10.1109\/SFCS.1985.43"},{"key":"17_CR14","unstructured":"R. Motwani, J. Naor, M. Naor. The probabilistic method yields deterministic parallel algorithms. Proc. 1989 IEEE FOCS, 8\u201313."},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"G. Pantziou, P. Spirakis, C. Zaroliagis. Fast parallel approximations of the maximum weighted cut problem through Derandomization. FST&TCS 9: 1989, Bangalore, India, LNCS 405, 20\u201329.","DOI":"10.1007\/3-540-52048-1_29"},{"issue":"4","key":"17_CR16","first-page":"130","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan. Probabilistic construction of deterministic algorithms: approximating packing integer programs. JCSS 37:4, Oct. 1988, 130\u2013143.","journal-title":"JCSS"},{"key":"17_CR17","volume-title":"Ten Lectures on the Probabilistic Method","author":"J. Spencer","year":"1987","unstructured":"J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, Philadelphia, 1987."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028260.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:58:35Z","timestamp":1607533115000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028260"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540543430"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0028260","relation":{},"subject":[]}}