{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:40:03Z","timestamp":1742593203251,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540520481"},{"type":"electronic","value":"9783540468721"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-52048-1_29","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:19:43Z","timestamp":1330204783000},"page":"20-29","source":"Crossref","is-referenced-by-count":7,"title":["Fast parallel approximations of the maximum weighted cut problem through derandomization"],"prefix":"10.1007","author":[{"given":"Grammati","family":"Pantziou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"Alon","year":"1986","unstructured":"[Alon, Babai, Itai, 86] \u201cA fast and simple Randomized parallel Algorithm for the Maximal Independent Set Problem\u201d, J. of Algorithms, 7, 567\u2013583, 1986.","journal-title":"J. of Algorithms"},{"key":"2_CR2","unstructured":"[Bernstein, 45] \u201cTheory of Probability\u201d, (3rd ed.), GTTI, Moscow, 1945."},{"issue":"1","key":"2_CR3","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"Cole","year":"1986","unstructured":"[Cole, Vishkin, 86] \u201cDeterministic Coin Tossing with Applications to Optimal Parallel List Ranking\u201d, Inform. and Control, Vol.70, N.1, pp. 32\u201353, July 1986.","journal-title":"Inform. and Control"},{"key":"2_CR4","unstructured":"[Garey, Johnsn, 79] \u201cComputers and Intractability \u2014 A Guide to the Theory of NP-Completeness\u201d, Ed. Freeman and Co, San Francisco, 2nd printing, 1979."},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"Garey","year":"1976","unstructured":"[Garey, Johnson, Stockmeyer, 76] \u201cSome Simplified NP-Complete Graph Problems\u201d, Theor. Comp. Science 1, 237\u2013267, 1976.","journal-title":"Theor. Comp. Science"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"[Goldberg, Spencer, 87] \u201cA new Parallel Algorithm for the Maximal Independent Set Problem\u201d, Proc. 28th IEEE FOCS, pp. 161\u2013165, 1987. Also in SIAM J. on Computing, April 1989, pp. 419\u2013427.","DOI":"10.1137\/0218029"},{"key":"2_CR7","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1214\/aop\/1176996762","volume":"2","author":"Joffe","year":"1974","unstructured":"[Joffe, 74] \u201cOn a set of almost deterministic k-independent random variables\u201d, Ann. Probability, 2 (1974), 161\u2013162.","journal-title":"Ann. Probability"},{"key":"2_CR8","unstructured":"[Karp, 72] \u201cReducibility among Combinatorial Problems\u201d, in \u201cComplexity of Computer Computations\u201d, Plenum Press, NY, 1972."},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"[Karp, Wigderson, 84] \u201cA Fast Parallel Algorithm for the Maximal Independent Set Problem\u201d, Proc. 16th ACM STOC, pp. 266\u2013272, 1984.","DOI":"10.1145\/800057.808690"},{"key":"2_CR10","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1214\/aoms\/1177700007","volume":"36","author":"Lancaster","year":"1965","unstructured":"[Lancaster, 65] \u201cPairwise Statistical Independence\u201d, Ann. Math. Stat. 36, (1965), 1313\u20131317.","journal-title":"Ann. Math. Stat."},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"[Luby, 85] \u201cA simple Parallel Algorithm for the Maximal Independent Set Problem\u201d, Proc. 17th ACM STOC, pp. 1\u201310, Providence RI, 1985.","DOI":"10.1145\/22145.22146"},{"key":"2_CR12","unstructured":"[Luby, 88] \u201cRemoving Randomness in Parallel Computation without a Processor Penalty\u201d, Proc. 29th IEEE FOCS, pp. 162\u2013174, 1988."},{"key":"2_CR13","series-title":"Techn. Rep.","volume-title":"Fast Parallel Approximations of the Maximum Weighted Cut Problem through Derandomization","author":"Pantziou","year":"1989","unstructured":"[Pantziou, Spirakis, Zaroliagis, 89] \u201cFast Parallel Approximations of the Maximum Weighted Cut Problem through Derandomization\u201d, Techn. Rep. TR-83.04.89, Computer Technology Institute, Patras, 1989."},{"key":"2_CR14","unstructured":"[Papoulis, 86] \u201cProbability, Random Variables and Stohastic Processes\u201d, 2nd edit., McCraw-Hill, 1986."},{"key":"2_CR15","unstructured":"[Valiant, 77] \u201cThe Complexity of enumeration and reliability problems\u201d, Report No. CSR-15-77, CS Dept, Univ. of Edinburg, Scottland."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52048-1_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:58:07Z","timestamp":1742590687000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52048-1_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540520481","9783540468721"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-52048-1_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}