{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T16:31:50Z","timestamp":1754152310373,"version":"3.41.2"},"reference-count":27,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["12101314"],"award-info":[{"award-number":["12101314"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["1187128"],"award-info":[{"award-number":["1187128"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["12271259"],"award-info":[{"award-number":["12271259"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004608","name":"Natural Science Foundation of Jiangsu Province","doi-asserted-by":"publisher","award":["BK20200723"],"award-info":[{"award-number":["BK20200723"]}],"id":[{"id":"10.13039\/501100004608","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Jiangsu Province Higher Education Foundation","award":["20KJB110022"],"award-info":[{"award-number":["20KJB110022"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:p> Sparsest cut problems are very important graph partitions, which have been widely applied in expander graphs, Markov chains, and image segmentation. In this paper, we study the edge-weighted version of the Sparse Cut Problem, which minimizes the ratio of the total weight of edges between blocks and the total weight of edges incident to vertices in one block. We first prove that the problem is even NP-hard for an edge-weighted graph with bridges. Then, we combine and generalize submodular functions and principal partition to design a graph algorithm to improve the initial bipartition, which runs in polynomial time by using network flow as its subroutines. <\/jats:p>","DOI":"10.1142\/s0129054122460029","type":"journal-article","created":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T22:29:50Z","timestamp":1674858590000},"page":"619-633","source":"Crossref","is-referenced-by-count":0,"title":["Graph Algorithm Based Submodular Function for Sparsest Cut Problem"],"prefix":"10.1142","volume":"36","author":[{"given":"Xiaoyan","family":"Zhang","sequence":"first","affiliation":[{"name":"School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Nanjing, 210023, P. R. China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0828-5189","authenticated-orcid":false,"given":"Hong","family":"Chang","sequence":"additional","affiliation":[{"name":"School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Nanjing, 210023, P. R. China"}]},{"given":"Longkun","family":"Guo","sequence":"additional","affiliation":[{"name":"School of Math and Statistics, Fuzhou University, Fuzhou, 350108, P. R. China"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[{"name":"Faculty of Management, University of New Brunswick, Fredericton, New Brunswick, Canada, E3B 5A3, Canada"}]},{"given":"Gaokai","family":"Zou","sequence":"additional","affiliation":[{"name":"School of Computer and Data Science, Fuzhou University, Fuzhou, 350108, P. R. China"}]},{"given":"Yuanyuan","family":"Xiong","sequence":"additional","affiliation":[{"name":"School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Nanjing, 210023, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2023,1,26]]},"reference":[{"key":"S0129054122460029BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"S0129054122460029BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"S0129054122460029BIB003","doi-asserted-by":"publisher","DOI":"10.1137\/080731049"},{"key":"S0129054122460029BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"S0129054122460029BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90071-0"},{"key":"S0129054122460029BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.12.008"},{"key":"S0129054122460029BIB007","first-page":"195","volume-title":"Problem in Analysis","author":"Cheeger J.","year":"1970"},{"issue":"6","key":"S0129054122460029BIB009","first-page":"726","volume":"57","author":"Chung F.","year":"2010","journal-title":"Notices of the American Mathematical Society"},{"key":"S0129054122460029BIB010","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.13.7.492"},{"key":"S0129054122460029BIB011","first-page":"697","volume-title":"Proceedings of the Calgary International Conference on Combinatorial Structures","author":"Edmonds J.","year":"1970"},{"key":"S0129054122460029BIB012","series-title":"Annals of Discrete Mathematics","volume-title":"Submodular functions and optimization","author":"Fujishige S.","year":"1991"},{"volume-title":"Computers and intractability, a guide to the theory of NP-completeness","year":"1979","author":"Garey M. R.","key":"S0129054122460029BIB013"},{"key":"S0129054122460029BIB014","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"S0129054122460029BIB016","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"S0129054122460029BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579322"},{"key":"S0129054122460029BIB018","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"volume-title":"Complexity Issues in VLSI: Optimal layout for the shuffle-exchange graph and other networks","year":"1983","author":"Leighton F. T.","key":"S0129054122460029BIB019"},{"key":"S0129054122460029BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"S0129054122460029BIB021","first-page":"270","volume-title":"Proceedings of the 21st Annual IEEESymposium on Foundations of Computer Science, IEEE Computer Society","author":"Leiserson C. E.","year":"1980"},{"key":"S0129054122460029BIB022","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"S0129054122460029BIB023","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.92"},{"key":"S0129054122460029BIB024","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214079"},{"key":"S0129054122460029BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90133-W"},{"key":"S0129054122460029BIB027","volume-title":"Annals of Discrete Mathematics","volume":"54","author":"Narayanan H.","year":"1997"},{"key":"S0129054122460029BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00472-9"},{"key":"S0129054122460029BIB030","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"issue":"2","key":"S0129054122460029BIB031","first-page":"96","volume":"421","author":"Spielmat D. A.","year":"1996","journal-title":"Linear Algebra Appl."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122460029","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T03:44:35Z","timestamp":1753155875000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122460029"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,26]]},"references-count":27,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["10.1142\/S0129054122460029"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122460029","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,1,26]]}}}