{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:04:32Z","timestamp":1757617472300,"version":"3.44.0"},"publisher-location":"Singapore","reference-count":29,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819610891"},{"type":"electronic","value":"9789819610907"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-1090-7_31","type":"book-chapter","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T16:33:17Z","timestamp":1741105997000},"page":"384-396","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Minimum Edge Bisection of\u00a0Graph"],"prefix":"10.1007","author":[{"given":"Kun","family":"You","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Tang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yifeng","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baoliu","family":"Ye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,3,5]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Abou-Rjeili, A., Karypis, G.: Multilevel algorithms for partitioning power-law graphs. In: Proceedings 20th IEEE International Parallel & Distributed Processing Symposium, p. 10 (2006)","DOI":"10.1109\/IPDPS.2006.1639360"},{"issue":"1","key":"31_CR2","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1080\/10586458.2001.10504428","volume":"10","author":"W Aiello","year":"2001","unstructured":"Aiello, W., Chung, F., Lu, L.: A random graph model for power law graphs. Exp. Math. 10(1), 53\u201366 (2001)","journal-title":"Exp. Math."},{"issue":"2","key":"31_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2), 1\u201337 (2009)","journal-title":"J. ACM"},{"key":"31_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/3-540-45465-9_53","volume-title":"Automata, Languages and Programming","author":"P Berman","year":"2002","unstructured":"Berman, P., Karpinski, M.: Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 623\u2013632. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45465-9_53"},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"Bourse, F., Lelarge, M., Vojnovic, M.: Balanced graph edge partition. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1456\u20131465 (2014)","DOI":"10.1145\/2623330.2623660"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Fan, W., et al.: Application driven graph partitioning. In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 1765\u20131779 (2020)","DOI":"10.1145\/3318464.3389745"},{"issue":"4","key":"31_CR7","doi-asserted-by":"publisher","first-page":"1090","DOI":"10.1137\/S0097539701387660","volume":"31","author":"U Feige","year":"2002","unstructured":"Feige, U., Krauthgamer, R.: A polylogarithmic approximation of the minimum bisection. SIAM J. Comput. 31(4), 1090\u20131118 (2002)","journal-title":"SIAM J. Comput."},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Feige, U., Krauthgamer, R., Nissim, K.: Approximating the minimum bisection size. In: Proceedings of the 32rd Annual ACM Symposium on Theory of Computing, pp. 530\u2013536 (2000)","DOI":"10.1145\/335305.335370"},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"Fiduccia, C.M., Mattheyses, R.M.: A linear-time heuristic for improving network partitions. In: Papers on Twenty-five Years of Electronic Design Automation, pp. 241\u2013247 (1988)","DOI":"10.1145\/62882.62910"},{"key":"31_CR10","unstructured":"Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., Guestrin, C.: PowerGraph: distributed graph-parallel computation on natural graphs. In: 10th USENIX Symposium on Operating Systems Design and Implementation, pp. 17\u201330 (2012)"},{"key":"31_CR11","unstructured":"Gonzalez, J.E., Xin, R.S., Dave, A., Crankshaw, D., Franklin, M.J., Stoica, I.: GraphX: Graph processing in a distributed dataflow framework. In: 11th USENIX Symposium on Operating Systems Design and Implementation, pp. 599\u2013613 (2014)"},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"Ji, S., Bu, C., Li, L., Wu, X.: Local graph edge partitioning with a two-stage heuristic method. In: IEEE 39th International Conference on Distributed Computing Systems, pp. 228\u2013237 (2019)","DOI":"10.1109\/ICDCS.2019.00031"},{"issue":"2","key":"31_CR13","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","volume":"49","author":"BW Kernighan","year":"1970","unstructured":"Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291\u2013307 (1970)","journal-title":"Bell Syst. Tech. J."},{"issue":"4","key":"31_CR14","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S Khot","year":"2006","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"key":"31_CR15","doi-asserted-by":"crossref","unstructured":"Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E.: Stochastic models for the web graph. In: Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 57\u201365 (2000)","DOI":"10.1109\/SFCS.2000.892065"},{"issue":"1","key":"31_CR16","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"J Leskovec","year":"2009","unstructured":"Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29\u2013123 (2009)","journal-title":"Internet Math."},{"issue":"12","key":"31_CR17","doi-asserted-by":"publisher","first-page":"1478","DOI":"10.14778\/2824032.2824046","volume":"8","author":"D Margo","year":"2015","unstructured":"Margo, D., Seltzer, M.: A scalable distributed graph partitioner. Proc. VLDB Endowment 8(12), 1478\u20131489 (2015)","journal-title":"Proc. VLDB Endowment"},{"key":"31_CR18","doi-asserted-by":"crossref","unstructured":"Mayer, C., et al.: ADWISE: adaptive window-based streaming edge partitioning for high-speed graph processing. In: IEEE 38th International Conference on Distributed Computing Systems, pp. 685\u2013695 (2018)","DOI":"10.1109\/ICDCS.2018.00072"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"McSherry, F.: Spectral partitioning of random graphs. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 529\u2013537 (2001)","DOI":"10.1109\/SFCS.2001.959929"},{"issue":"18","key":"31_CR20","doi-asserted-by":"publisher","first-page":"7332","DOI":"10.1073\/pnas.0610245104","volume":"104","author":"JP Onnela","year":"2007","unstructured":"Onnela, J.P., Saram\u00e4ki, J., Hyv\u00f6nen, J., Szab\u00f3, G., Lazer, D., Kaski, K., Kert\u00e9sz, J., Barab\u00e1si, A.L.: Structure and tie strengths in mobile communication networks. Proc. Natl. Acad. Sci. 104(18), 7332\u20137336 (2007)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"31_CR21","doi-asserted-by":"crossref","unstructured":"Petroni, F., Querzoni, L., Daudjee, K., Kamali, S., Iacoboni, G.: HDRF: stream-based partitioning for power-law graphs. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 243\u2013252 (2015)","DOI":"10.1145\/2806416.2806424"},{"key":"31_CR22","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 255\u2013264 (2008)","DOI":"10.1145\/1374376.1374415"},{"key":"31_CR23","doi-asserted-by":"crossref","unstructured":"Roy, A., Bindschaedler, L., Malicevic, J., Zwaenepoel, W.: Chaos: scale-out graph processing from secondary storage. In: Proceedings of the 25th Symposium on Operating Systems Principles, pp. 410\u2013424 (2015)","DOI":"10.1145\/2815400.2815408"},{"key":"31_CR24","doi-asserted-by":"publisher","unstructured":"Saran, Huzur, Vazirani, Vijay V..: Finding k cuts within twice the optimal. SIAM J. Comput. 24(1), 101\u2013108 (1995). https:\/\/doi.org\/10.1137\/S0097539792251730","DOI":"10.1137\/S0097539792251730"},{"key":"31_CR25","doi-asserted-by":"crossref","unstructured":"Stanton, I., Kliot, G.: Streaming graph partitioning for large distributed graphs. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1222\u20131230 (2012)","DOI":"10.1145\/2339530.2339722"},{"key":"31_CR26","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C., Gkantsidis, C., Radunovic, B., Vojnovic, M.: FENNEL: streaming graph partitioning for massive scale graphs. In: Proceedings of the 7th ACM International Conference on Web Search and Data Mining, pp. 333\u2013342 (2014)","DOI":"10.1145\/2556195.2556213"},{"key":"31_CR27","doi-asserted-by":"crossref","unstructured":"Wang, L., Xiao, Y., Shao, B., Wang, H.: How to partition a billion-node graph. In: IEEE 30th International Conference on Data Engineering, pp. 568\u2013579 (2014)","DOI":"10.1109\/ICDE.2014.6816682"},{"key":"31_CR28","unstructured":"Xie, C., Yan, L., Li, W.J., Zhang, Z.: Distributed power-law graph computing: Theoretical and empirical analysis. In: Advances in Neural Information Processing Systems, vol. 27 (2014)"},{"key":"31_CR29","doi-asserted-by":"crossref","unstructured":"Zhang, C., Wei, F., Liu, Q., Tang, Z.G., Li, Z.: Graph edge partitioning via neighborhood heuristic. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 605\u2013614 (2017)","DOI":"10.1145\/3097983.3098033"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-1090-7_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T07:08:25Z","timestamp":1757142505000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-1090-7_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819610891","9789819610907"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-1090-7_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"5 March 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/anl.sjtu.edu.cn\/cocoon2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}