{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:56:47Z","timestamp":1725573407022},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540309352"},{"type":"electronic","value":"9783540324263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11602613_48","type":"book-chapter","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T08:24:24Z","timestamp":1133511864000},"page":"473-482","source":"Crossref","is-referenced-by-count":0,"title":["Boosting Spectral Partitioning by Sampling and Iteration"],"prefix":"10.1007","author":[{"given":"Joachim","family":"Giesen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Mitsche","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"48_CR1","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"},{"issue":"2","key":"48_CR2","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":"48_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z","volume":"10","author":"A. Frieze","year":"1997","unstructured":"Frieze, A., McDiarmid, C.: Algorithmic theory of random graphs. Random Structures and Algorithms\u00a010, 5\u201342 (1997)","journal-title":"Random Structures and Algorithms"},{"key":"48_CR4","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":"48_CR5","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":"48_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/11604686_36","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Giesen","year":"2005","unstructured":"Giesen, J., Mitsche, D.: Bounding the misclassification error in spectral partitioning in the planted partition model. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 409\u2013420. Springer, Heidelberg (2005)"},{"key":"48_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/11537311_38","volume-title":"Fundamentals of Computation Theory","author":"J. Giesen","year":"2005","unstructured":"Giesen, J., Mitsche, D.: Reconstructing many partitions using spectral techniques. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol.\u00a03623, pp. 433\u2013444. Springer, Heidelberg (2005)"},{"key":"48_CR8","unstructured":"Krivelevich, M., Vu, V.H.: On the concentration of eigenvalues of random symmetric matrices. Microsoft Technical Report\u00a060 (2000)"},{"key":"48_CR9","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":"48_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/3-540-45471-3_24","volume-title":"Algorithm Theory - SWAT 2002","author":"R. Shamir","year":"2002","unstructured":"Shamir, R., Tsur, D.: Improved algorithms for the random cluster graph model. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol.\u00a02368, pp. 230\u2013259. Springer, Heidelberg (2002)"},{"key":"48_CR11","volume-title":"Matrix perturbation theory","author":"G. Stewart","year":"1990","unstructured":"Stewart, G., Sun, J.: Matrix perturbation theory. Academic Press, Boston (1990)"},{"key":"48_CR12","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","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11602613_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:02:54Z","timestamp":1619506974000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11602613_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309352","9783540324263"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/11602613_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}