{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T04:04:12Z","timestamp":1750478652082,"version":"3.41.0"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"4-5","license":[{"start":{"date-parts":[[2004,9,24]],"date-time":"2004-09-24T00:00:00Z","timestamp":1095984000000},"content-version":"unspecified","delay-in-days":85,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2004,7]]},"abstract":"<jats:p>We give an algorithm that, with high probability, recovers a planted <jats:inline-formula>$k$<\/jats:inline-formula>-partition in a random graph, where edges within vertex classes occur with probability <jats:inline-formula>$p$<\/jats:inline-formula> and edges between vertex classes occur with probability <jats:inline-formula>$r\\ge p+c\\sqrt{p\\log n\/n}$<\/jats:inline-formula>. The algorithm can handle vertex classes of different sizes and, for fixed <jats:inline-formula>$k$<\/jats:inline-formula>, runs in linear time. We also give variants of the algorithm for partitioning matrices and hypergraphs.<\/jats:p>","DOI":"10.1017\/s0963548304006303","type":"journal-article","created":{"date-parts":[[2004,9,24]],"date-time":"2004-09-24T13:28:19Z","timestamp":1096032499000},"page":"451-474","source":"Crossref","is-referenced-by-count":11,"title":["Max Cut for Random Graphs with a Planted Partition"],"prefix":"10.1017","volume":"13","author":[{"given":"B.","family":"BOLLOB\u00c1S","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. D.","family":"SCOTT","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2004,9,24]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548304006303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T15:47:59Z","timestamp":1750434479000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548304006303\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":0,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["S0963548304006303"],"URL":"https:\/\/doi.org\/10.1017\/s0963548304006303","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2004,7]]}}}