{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:02:36Z","timestamp":1725552156305},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540310006"},{"type":"electronic","value":"9783540314684"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11604686_36","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T15:02:01Z","timestamp":1133794921000},"page":"409-420","source":"Crossref","is-referenced-by-count":2,"title":["Bounding the Misclassification Error in Spectral Partitioning in the Planted Partition Model"],"prefix":"10.1007","author":[{"given":"Joachim","family":"Giesen","sequence":"first","affiliation":[]},{"given":"Dieter","family":"Mitsche","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W","volume":"13","author":"N. Alon","year":"1998","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. Random Structures and Algorithms\u00a013, 457\u2013466 (1998)","journal-title":"Random Structures and Algorithms"},{"key":"36_CR2","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1017\/S0963548304006303","volume":"13","author":"B. Bollobas","year":"2004","unstructured":"Bollobas, B., Scott, A.D.: Max cut for random graphs with a planted partition. Combinatorics, Probability and Computing\u00a013, 451\u2013474 (2004)","journal-title":"Combinatorics, Probability and Computing"},{"key":"36_CR3","doi-asserted-by":"crossref","unstructured":"Boppana, R.B.: Eigenvalues and graph bisection: An average-case analysis. In: Proceedings of 28th IEEE Symposium on Foundations on Computer Science, pp. 280\u2013285 (1987)","DOI":"10.1109\/SFCS.1987.22"},{"issue":"2","key":"36_CR4","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1002\/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2","volume":"8","author":"A. Condon","year":"1999","unstructured":"Condon, A., Karp, R.: Algorithms for graph partitioning on the planted partition model. Random Structures and Algorithms\u00a08(2), 116\u2013140 (1999)","journal-title":"Random Structures and Algorithms"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF02579329","volume":"3","author":"Z. F\u00fcredi","year":"1981","unstructured":"F\u00fcredi, Z., Koml\u00f3s, J.: The eigenvalues of random symmetric matrices. Combinatorica I\u00a03, 233\u2013241 (1981)","journal-title":"Combinatorica I"},{"key":"36_CR6","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete graph problems. Theoretical Computer Science\u00a01, 237\u2013267 (1976)","journal-title":"Theoretical Computer Science"},{"key":"36_CR7","unstructured":"Krivelevich, M., Vu, V.H.: On the concentration of eigenvalues of random symmetric matrices. Microsoft Technical Report, 60 (2000)"},{"key":"36_CR8","doi-asserted-by":"crossref","unstructured":"McSherry, F.: Spectral partitioning of random graphs. In: Proceedings of 42nd IEEE Symosium on Foundations of Computer Science, pp. 529\u2013537 (2001)","DOI":"10.1109\/SFCS.2001.959929"},{"key":"36_CR9","unstructured":"Meila, M., Verma, D.: A comparison of spectral clustering algorithms. UW CSE Technical report 03-05-01"},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"Shamir, R., Tsur, D.: Improved algorithms for the random cluster graph model. In: Proceedings 7th Scandinavian Workshop on Algorithm Theory, pp. 230\u2013259 (2002)","DOI":"10.1007\/3-540-45471-3_24"},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"Spielman, D., Teng, S.-H.: Spectral partitioning works: Planar graphs and finite element meshes. In: Proceedings of 37th IEEE Symposium on Foundations on Computer Science, pp. 96\u2013105 (1996)","DOI":"10.1109\/SFCS.1996.548468"},{"key":"36_CR12","volume-title":"Matrix perturbation theory","author":"G. Stewart","year":"1990","unstructured":"Stewart, G., Sun, J.: Matrix perturbation theory. Academic Press, Boston (1990)"},{"key":"36_CR13","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1145\/1060590.1060654","volume-title":"STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing","author":"V.H. Vu","year":"2005","unstructured":"Vu, V.H.: Spectral norm of random matrices. In: STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 423\u2013430. ACM Press, New York (2005)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11604686_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:04:28Z","timestamp":1619507068000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11604686_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540310006","9783540314684"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11604686_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}