{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:36:48Z","timestamp":1725475008005},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540496946"},{"type":"electronic","value":"9783540496960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11940128_51","type":"book-chapter","created":{"date-parts":[[2006,11,29]],"date-time":"2006-11-29T00:57:35Z","timestamp":1164761855000},"page":"507-516","source":"Crossref","is-referenced-by-count":2,"title":["A Simple Message Passing Algorithm for Graph Partitioning Problems"],"prefix":"10.1007","author":[{"given":"Mikael","family":"Onsj\u00f6","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"51_CR1","doi-asserted-by":"crossref","unstructured":"Boppana, R.B.: Eigenvalues and graph bisection: an average-case analysis. In: Proc. Symposium on Foundations of Computer Science, pp. 280\u2013285 (1987)","DOI":"10.1109\/SFCS.1987.22"},{"key":"51_CR2","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"T. Bui","year":"1987","unstructured":"Bui, T., Chaudhuri, S., Leighton, F., Spiser, M.: Graph bisection algorithms with good average behavior. Combinatorica\u00a07, 171\u2013191 (1987)","journal-title":"Combinatorica"},{"key":"51_CR3","unstructured":"Coja-Oghlan, A.: A spectral heuristic for bisecting random graphs. In: Proc. SODA 2005, pp. 850\u2013859 (2005), (The journal version will appear Random Structures and Algorithms)"},{"key":"51_CR4","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1002\/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2","volume":"18","author":"A. Condon","year":"2001","unstructured":"Condon, A., Karp, R.: Algorithms for graph partitioning on the planted partition model. Random Str. and Algorithms\u00a018, 116\u2013140 (2001)","journal-title":"Random Str. and Algorithms"},{"key":"51_CR5","doi-asserted-by":"crossref","unstructured":"Dubhashi, D., Laura, L., Panconesi, A.: Analysis and experimental evaluation of a simple algorithm for collaborative filtering in planted partition models. In: Proc. FST TCS 2003, pp. 168\u2013182 (2003)","DOI":"10.1007\/978-3-540-24597-1_15"},{"key":"51_CR6","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/0196-6774(89)90001-1","volume":"10","author":"M.E. Dyer","year":"1989","unstructured":"Dyer, M.E., Frieze, A.M.: The solution of some random NP-hard problems in polynomial expected time. J. of Algorithms\u00a010, 451\u2013489 (1989)","journal-title":"J. of Algorithms"},{"key":"51_CR7","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, Bell Telephone Laboratories, Incorporated (1979)"},{"key":"51_CR8","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci.\u00a01, 237\u2013267 (1976)","journal-title":"Theoret. Comput. Sci."},{"issue":"1-3","key":"51_CR9","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(97)00133-9","volume":"82","author":"M. Jerrum","year":"1998","unstructured":"Jerrum, M., Sorkin, G.: The Metropolis algorithm for graph bisection. Discrete Appl. Math.\u00a082(1-3), 155\u2013175 (1998)","journal-title":"Discrete Appl. Math."},{"key":"51_CR10","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1162\/089976603321192103","volume":"15","author":"R. Hahnloser","year":"2003","unstructured":"Hahnloser, R., Seung, H., Slotine, J.: Permitted and forbidden sets in threshold-linear networks. Neural Computation\u00a015, 621\u2013638 (2003)","journal-title":"Neural Computation"},{"key":"51_CR11","first-page":"529","volume-title":"Proc. 40th IEEE Sympos. on Foundations of Computer Science (FOCS 1999)","author":"F.M. Sherry","year":"1999","unstructured":"McSherry, F.: Spectral partition of random graphs. In: Proc. 40th IEEE Sympos. on Foundations of Computer Science (FOCS 1999), pp. 529\u2013537. IEEE, Los Alamitos (1999)"},{"key":"51_CR12","unstructured":"Onsj\u00f6, M.: Master Thesis (2005)"},{"key":"51_CR13","unstructured":"Onsj\u00f6, M., Watanabe, O.: Simple algorithms for graph partition problems, Research Report C-212, Dept. of Math. and Comput. Sci., Tokyo Inst. of Tech. (2005)"},{"key":"51_CR14","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"J. Pearl","year":"1988","unstructured":"Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., San Francisco (1988)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11940128_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:50:01Z","timestamp":1619495401000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11940128_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540496946","9783540496960"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11940128_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}