{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T12:30:36Z","timestamp":1753273836799},"reference-count":20,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2003,9,1]],"date-time":"2003-09-01T00:00:00Z","timestamp":1062374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3643,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,9]]},"DOI":"10.1016\/s0166-218x(02)00472-9","type":"journal-article","created":{"date-parts":[[2003,7,16]],"date-time":"2003-07-16T10:54:32Z","timestamp":1058352872000},"page":"535-553","source":"Crossref","is-referenced-by-count":8,"title":["Improving graph partitions using submodular functions"],"prefix":"10.1016","volume":"131","author":[{"given":"Sachin B.","family":"Patkar","sequence":"first","affiliation":[]},{"given":"H.","family":"Narayanan","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(02)00472-9_BIB1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0166-218X(98)00083-3","article-title":"Spectral Partitioning with multiple eigenvectors","volume":"90","author":"Alpert","year":"1999","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(02)00472-9_BIB2","doi-asserted-by":"crossref","unstructured":"C.J. Alpert, S.Z. Yao, Spectral partitioning: the more eigenvectors, the better, Proceedings of 32nd Design Automation Conference, 1995, pp. 195\u2013200.","DOI":"10.1109\/DAC.1995.250089"},{"key":"10.1016\/S0166-218X(02)00472-9_BIB3","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1006\/jagm.1999.1062","article-title":"Greedily finding a dense subgraph","volume":"34","author":"Asahiro","year":"2000","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00472-9_BIB4","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0020-0190(94)90013-2","article-title":"A faster algorithm for computing the strength of a network","volume":"49","author":"Cheng","year":"1994","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(02)00472-9_BIB5","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1287\/mnsc.13.7.492","article-title":"On nonlinear fractional programming","volume":"13","author":"Dinkelbach","year":"1967","journal-title":"Manage. Sci."},{"key":"10.1016\/S0166-218X(02)00472-9_BIB6","unstructured":"J. Edmonds, Submodular functions, matroids and certain polyhedra, Proceedings of the Calgary International Conference on Combinatorial Structures, 1970, pp. 69\u201387."},{"key":"10.1016\/S0166-218X(02)00472-9_BIB7","unstructured":"U. Feige, G. Kortsarz, D. Peleg, The densest k-subgraph problem, Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993, pp. 692\u2013701."},{"key":"10.1016\/S0166-218X(02)00472-9_BIB8","series-title":"Submodular Functions and Optimization, Annals of Discrete Mathematics","author":"Fujishige","year":"1991"},{"key":"10.1016\/S0166-218X(02)00472-9_BIB9","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1006\/jagm.1997.0904","article-title":"Algorithms for graphic polymatroids and parametric s-sets","volume":"26","author":"Gabow","year":"1998","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00472-9_BIB10","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0218003","article-title":"A fast parametric network flow algorithm","volume":"18","author":"Gallo","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(02)00472-9_BIB11","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","article-title":"A new approach to the maximum flow problem","volume":"35","author":"Goldberg","year":"1988","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0166-218X(02)00472-9_BIB12","doi-asserted-by":"crossref","unstructured":"O. Goldschmidt, D. Hochbaum, Polynomial algorithm for the k-cut problem, 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 444\u2013451.","DOI":"10.1109\/SFCS.1988.21960"},{"key":"10.1016\/S0166-218X(02)00472-9_BIB13","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1137\/0220040","article-title":"Computing the strength of a graph","volume":"20","author":"Gusfield","year":"1991","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(02)00472-9_BIB14","doi-asserted-by":"crossref","unstructured":"F.T. Leighton, S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximate algorithms, 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 422\u2013431.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"10.1016\/S0166-218X(02)00472-9_BIB15","series-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"Lengauer","year":"1990"},{"key":"10.1016\/S0166-218X(02)00472-9_BIB16","article-title":"Submodular Functions and Electrical Networks","volume":"Vol. 54","author":"Narayanan","year":"1997"},{"key":"10.1016\/S0166-218X(02)00472-9_BIB17","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1006\/jagm.1996.0047","article-title":"Approximation algorithms for min-k-overlap problems, using the principal lattice of partitions approach","volume":"21","author":"Narayanan","year":"1996","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00472-9_BIB18","unstructured":"S.B. Patkar, H. Narayanan, Fast on-line\/off-line algorithms for optimal reinforcement of a network and its connections with principal partition, Proceedings of 20th Annual Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 1974, Springer, Berlin, 2000, pp. 94\u2013105."},{"key":"10.1016\/S0166-218X(02)00472-9_BIB19","first-page":"394","article-title":"Selected applications of minimum cuts in networks","volume":"20","author":"Picard","year":"1982","journal-title":"INFOR-Canada J. Oper. Res. Inform. Process."},{"key":"10.1016\/S0166-218X(02)00472-9_BIB20","unstructured":"N. Tomizawa, S. Fujishige, Historical survey of extensions of the concept of principal partition and their unifying generalization to hypermatriods, Systems Science Research Report No. 5, Department of Systems Science, Tokyo Institute of Technology, April 1982 (also its abridgment in Proceedings of the 1982 IEEE International Symposium on Circuits and Systems Rome, 1982, pp. 142\u2013145)."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02004729?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02004729?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,17]],"date-time":"2019-03-17T09:51:35Z","timestamp":1552816295000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X02004729"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,9]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,9]]}},"alternative-id":["S0166218X02004729"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00472-9","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2003,9]]}}}