{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:47Z","timestamp":1763468087508,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325113"},{"type":"electronic","value":"9783642325120"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_52","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"615-626","source":"Crossref","is-referenced-by-count":4,"title":["Finding Small Sparse Cuts by Random Walk"],"prefix":"10.1007","author":[{"given":"Tsz Chiu","family":"Kwok","sequence":"first","affiliation":[]},{"given":"Lap Chi","family":"Lau","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"52_CR1","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","volume":"38","author":"N. Alon","year":"1985","unstructured":"Alon, N., Milman, V.: Isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B\u00a038(1), 73\u201388 (1985)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"Anderson, R., Chung, F.R.K., Lang, K.J.: Local graph partitioning using PageRank vectors. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 475\u2013486 (2006)","DOI":"10.1109\/FOCS.2006.44"},{"key":"52_CR3","doi-asserted-by":"crossref","unstructured":"Anderson, R., Peres, Y.: Finding sparse cuts locally using evolving sets. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 235\u2013244 (2009)","DOI":"10.1145\/1536414.1536449"},{"key":"52_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 563\u2013572 (2010)","DOI":"10.1109\/FOCS.2010.59"},{"key":"52_CR5","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"key":"52_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Nagarajan, V., Naor, J., Schwartz, R.: Min-max graph partitioning and small set expansion. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 17\u201326 (2011)","DOI":"10.1109\/FOCS.2011.79"},{"key":"52_CR7","doi-asserted-by":"crossref","unstructured":"Cheeger, J.: A lower bound for the smallest eigenvalue of the Laplacian. In: Problems in Analysis, pp. 195\u2013199. Princeton University Press (1970)","DOI":"10.1515\/9781400869312-013"},{"key":"52_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/978-3-540-95995-3_6","volume-title":"Algorithms and Models for the Web-Graph","author":"F. Chung","year":"2009","unstructured":"Chung, F.: A Local Graph Partitioning Algorithm Using Heat Kernel Pagerank. In: Avrachenkov, K., Donato, D., Litvak, N. (eds.) WAW 2009. LNCS, vol.\u00a05427, pp. 62\u201375. Springer, Heidelberg (2009)"},{"issue":"4","key":"52_CR9","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Horry","year":"2006","unstructured":"Horry, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bulletin of the American Mathematical Society\u00a043(4), 439\u2013561 (2006)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"52_CR10","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Oveis Gharan, S., Trevisan, L.: Multi-way spectral partitioning and higher-order Cheeger inequalities. In: Proceedings of the 44th Annual Symposium on Theory of Computing (STOC), pp. 1117\u20131130 (2012)","DOI":"10.1145\/2213977.2214078"},{"issue":"6","key":"52_CR11","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"F.T. Leighton","year":"1999","unstructured":"Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorem and their use in designing approximation algorithms. Journal of the ACM\u00a046(6), 787\u2013832 (1999)","journal-title":"Journal of the ACM"},{"key":"52_CR12","doi-asserted-by":"crossref","unstructured":"Louis, A., Raghavendra, P., Tetali, P., Vempala, S.: Many sparse cuts via higher eigenvalues. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 1131\u20131140 (2012)","DOI":"10.1145\/2213977.2214079"},{"key":"52_CR13","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Kannan, R.: Faster mixing via average conductance. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 282\u2013287 (1999)","DOI":"10.1145\/301250.301317"},{"key":"52_CR14","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Simonovits, M.: The mixing time of Markov chains, an isoperimetric inequality, and computing the volume. In: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 346\u2013354 (1990)","DOI":"10.1109\/FSCS.1990.89553"},{"key":"52_CR15","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pp. 755\u2013764 (2010)","DOI":"10.1145\/1806689.1806792"},{"key":"52_CR16","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D., Tetali, P.: Approximations for the isoperimetric and spectral profile of graphs and related parameters. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pp. 631\u2013640 (2010)","DOI":"10.1145\/1806689.1806776"},{"key":"52_CR17","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D., Tulsiani, M.: Reductions between expansion problems. In: Proceedings of the 27th Annual IEEE Conference on Computational Complexity, CCC (2012)","DOI":"10.1109\/CCC.2012.43"},{"key":"52_CR18","unstructured":"Spielman, D.A., Teng, S.-H.: A local clustering algorithm for massive graphs and its applications to nearly-linear time graph partitioning. CoRR, abs\/0809.3232 (2008)"},{"key":"52_CR19","doi-asserted-by":"crossref","unstructured":"Orecchia, L., Sachdeva, S., Vishnoi, N.K.: Approximating the exponential, the Lanczos method, and an $\\tilde{O}(m)$ -time spectral algorithm for balanced separator. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 1141\u20131160 (2012)","DOI":"10.1145\/2213977.2214080"},{"key":"52_CR20","doi-asserted-by":"crossref","unstructured":"Oveis Gharan, S., Trevisan, L.: Approximating the expansion profile and almost optimal local graph clustering. CoRR, abs\/1204.2021 (2012)","DOI":"10.1109\/FOCS.2012.85"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_52.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T03:25:30Z","timestamp":1743823530000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}