{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:21:23Z","timestamp":1725571283805},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175138"},{"type":"electronic","value":"9783642175145"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17514-5_33","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T20:09:23Z","timestamp":1291406963000},"page":"387-398","source":"Crossref","is-referenced-by-count":1,"title":["Beyond Good Shapes: Diffusion-Based Graph Partitioning Is Relaxed Cut Optimization"],"prefix":"10.1007","author":[{"given":"Henning","family":"Meyerhenke","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"33_CR1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. J.\u00a0Wiley & Sons, Chichester (2000)","edition":"2"},{"key":"33_CR2","volume-title":"Nonlinear Programming. Theory and Algorithms","author":"M.S. Bazaraa","year":"1993","unstructured":"Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming. Theory and Algorithms, 2nd edn. John Wiley, Chichester (1993)","edition":"2"},{"key":"33_CR3","volume-title":"Algebraic Graph Theory","author":"N. Biggs","year":"1993","unstructured":"Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1993)"},{"issue":"6-8","key":"33_CR4","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/j.parco.2007.12.001","volume":"34","author":"C. Chevalier","year":"2008","unstructured":"Chevalier, C., Pellegrini, F.: Pt-scotch: A tool for efficient parallel graph ordering. Parallel Comput.\u00a034(6-8), 318\u2013331 (2008)","journal-title":"Parallel Comput."},{"key":"33_CR5","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/BF01591018","volume":"25","author":"M. Fiedler","year":"1975","unstructured":"Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal\u00a025, 619\u2013633 (1975)","journal-title":"Czechoslovak Mathematical Journal"},{"issue":"3","key":"33_CR6","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TPAMI.2006.57","volume":"28","author":"L. Grady","year":"2006","unstructured":"Grady, L., Schwartz, E.L.: Isoperimetric graph partitioning for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell.\u00a028(3), 469\u2013475 (2006)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"33_CR7","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198572237.001.0001","volume-title":"Probability and Random Processes","author":"G.R. Grimmett","year":"2001","unstructured":"Grimmett, G.R., Stirzaker, D.R.: Probability and Random Processes, 3rd edn. Oxford University Press, Oxford (2001)","edition":"3"},{"issue":"2","key":"33_CR8","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1137\/0916028","volume":"16","author":"B. Hendrickson","year":"1995","unstructured":"Hendrickson, B., Leland, R.: An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM Journal on Scientific Computing\u00a016(2), 452\u2013469 (1995)","journal-title":"SIAM Journal on Scientific Computing"},{"issue":"1","key":"33_CR9","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1006\/jpdc.1997.1404","volume":"48","author":"G. Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing\u00a048(1), 96\u2013129 (1998)","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"33_CR10","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","volume":"49","author":"B.W. Kernighan","year":"1970","unstructured":"Kernighan, B.W., Lin, S.: An efficient heuristic for partitioning graphs. Bell Systems Technical Journal\u00a049, 291\u2013308 (1970)","journal-title":"Bell Systems Technical Journal"},{"issue":"2","key":"33_CR11","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S.P. Lloyd","year":"1982","unstructured":"Lloyd, S.P.: Least squares quantization in PCM. IEEE Transactions on Information Theory\u00a028(2), 129\u2013136 (1982)","journal-title":"IEEE Transactions on Information Theory"},{"key":"33_CR12","first-page":"1","volume":"2","author":"L. Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L.: Random walks on graphs: A survey. Combinatorics, Paul Erd\u00f6s is Eighty\u00a02, 1\u201346 (1993)","journal-title":"Combinatorics, Paul Erd\u00f6s is Eighty"},{"key":"33_CR13","unstructured":"Meila, M., Shi, J.: A random walks view of spectral segmentation. In: Eighth International Workshop on Artificial Intelligence and Statistics (AISTATS) (2001)"},{"issue":"9","key":"33_CR14","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1016\/j.jpdc.2009.04.005","volume":"69","author":"H. Meyerhenke","year":"2009","unstructured":"Meyerhenke, H., Monien, B., Sauerwald, T.: A new diffusion-based multilevel algorithm for computing graph partitions. Journal of Parallel and Distributed Computing\u00a069(9), 750\u2013761 (2009); Best Paper Awards and Panel Summary: IPDPS 2008","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"10-11","key":"33_CR15","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1016\/j.parco.2009.09.006","volume":"35","author":"H. Meyerhenke","year":"2009","unstructured":"Meyerhenke, H., Monien, B., Schamberger, S.: Graph partitioning and disturbed diffusion. Parallel Computing\u00a035(10-11), 544\u2013569 (2009)","journal-title":"Parallel Computing"},{"key":"33_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/11940128_44","volume-title":"Algorithms and Computation","author":"H. Meyerhenke","year":"2006","unstructured":"Meyerhenke, H., Sauerwald, T.: Analyzing disturbed diffusion on networks. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol.\u00a04288, pp. 429\u2013438. Springer, Heidelberg (2006)"},{"key":"33_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-540-74466-5_22","volume-title":"Euro-Par 2007 Parallel Processing","author":"F. Pellegrini","year":"2007","unstructured":"Pellegrini, F.: A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries. In: Kermarrec, A.-M., Boug\u00e9, L., Priol, T. (eds.) Euro-Par 2007. LNCS, vol.\u00a04641, pp. 195\u2013204. Springer, Heidelberg (2007)"},{"issue":"1","key":"33_CR18","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","volume":"1","author":"S.E. Schaeffer","year":"2007","unstructured":"Schaeffer, S.E.: Graph clustering. Computer Science Review\u00a01(1), 27\u201364 (2007)","journal-title":"Computer Science Review"},{"key":"33_CR19","first-page":"491","volume-title":"The Sourcebook of Parallel Computing","author":"K. Schloegel","year":"2003","unstructured":"Schloegel, K., Karypis, G., Kumar, V.: Graph partitioning for high performance scientific simulations. In: The Sourcebook of Parallel Computing, pp. 491\u2013541. Morgan Kaufmann, San Francisco (2003)"},{"issue":"8","key":"33_CR20","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J. Shi","year":"2000","unstructured":"Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a022(8), 888\u2013905 (2000)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"33_CR21","unstructured":"Walshaw, C.: The graph partitioning archive (2010), http:\/\/staffweb.cms.gre.ac.uk\/~c.walshaw\/partition\/ (Last access: 1 March 2010)"},{"key":"33_CR22","first-page":"1057","volume-title":"Proceedings of Advances in Neural Information Processing Systems 14 (NIPS 2001)","author":"H. Zha","year":"2001","unstructured":"Zha, H., He, X., Ding, C.H.Q., Gu, M., Simon, H.D.: Spectral relaxation for k-means clustering. In: Proceedings of Advances in Neural Information Processing Systems 14 (NIPS 2001), pp. 1057\u20131064. MIT Press, Cambridge (2001)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17514-5_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T19:12:31Z","timestamp":1711998751000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17514-5_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175138","9783642175145"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17514-5_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}