{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T03:11:28Z","timestamp":1780629088896,"version":"3.54.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1998,4,1]],"date-time":"1998-04-01T00:00:00Z","timestamp":891388800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1998,4]]},"DOI":"10.1007\/bf01581107","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T09:36:37Z","timestamp":1114680997000},"page":"229-256","source":"Crossref","is-referenced-by-count":62,"title":["The node capacitated graph partitioning problem: A computational study"],"prefix":"10.1007","volume":"81","author":[{"given":"C. E.","family":"Ferreira","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A.","family":"Martin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C. C.","family":"de Souza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Weismantel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L. A.","family":"Wolsey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","unstructured":"D. Applegate, R.E. Bixby, V. Chv\u00e1tal, W. Cook, Finding cuts in the TSP, DIMACS Technical Report, 1994, pp. 95\u201305."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/0010-4655(88)90002-1","volume":"49","author":"F. Barahona","year":"1988","unstructured":"F. Barahona, A. Casari, On the magnetisation of the ground states in two dimensional Ising spin glasses, Computer Physics Communications 49 (1988) 417\u2013421.","journal-title":"Computer Physics Communications"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F. Barahona","year":"1988","unstructured":"F. Barahona, M. Gr\u00f6tschel, M. J\u00fcnger, G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design, Operations Research 36 (1988) 493\u2013513.","journal-title":"Operations Research"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F. Barahona","year":"1986","unstructured":"F. Barahona, A. Mahjoub, On the cut polytope, Mathematical Programming 36 (1986) 157\u2013173.","journal-title":"Mathematical Programming"},{"key":"CR5","volume-title":"Optimisation des Fonctions Quadratiques en Variables Bivalentes","author":"N. Boissin","year":"1994","unstructured":"N. Boissin, Optimisation des Fonctions Quadratiques en Variables Bivalentes, Th\u00e8se de Doctorat, Conservatoire National des Arts et M\u00e9tiers, Paris, 1994."},{"key":"CR6","volume-title":"A branch-and-cut algorithm for the resolution of the equicut problem, Working Paper no. 361","author":"L. Brunetta","year":"1993","unstructured":"L. Brunetta, M. Conforti, G. Rinaldi, A branch-and-cut algorithm for the resolution of the equicut problem, Working Paper no. 361, IASI-CNR, Rome, 1993."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/net.3230210106","volume":"21","author":"S. Chopra","year":"1991","unstructured":"S. Chopra, M.R. Rao, On the multiway cut polyhedron, Networks 21 (1991) 51\u201389.","journal-title":"Networks"},{"key":"CR8","first-page":"247","volume":"74","author":"C.E. Ferreira","year":"1996","unstructured":"C.E. Ferreira, A. Martin, C.C. de Souza, R. Weismantel, L.A. Wolsey, The node capacitated graph partitioning problems: formulations and valid inequalities, Mathematical Programming 74 (1996) 247\u2013267.","journal-title":"Mathematical Programming"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"858","DOI":"10.1137\/S1052623493254455","volume":"6","author":"C.E. Ferreira","year":"1996","unstructured":"C.E. Ferreira, A. Martin, R. Weismantel, A cutting plane based algorithm for the multiple knapsack problem, SIAM J. on Optimization 6 (1996) 858\u2013877.","journal-title":"SIAM J. on Optimization"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"C.M. Fiduccia, R.M. Mattheyses, A linear time heuristic for improving network partitionings, in: Proceedings of the 19th Design Automation Conference, Las Vegas, 1982, pp. 175\u2013181.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01589097","volume":"45","author":"M. Gr\u00f6tschel","year":"1989","unstructured":"M. Gr\u00f6tschel, Y. Wakbayashi, A cutting plane algorithm for a clustering problem, Mathematical Programming Series B 45 (1989) 59\u201396.","journal-title":"Mathematical Programming Series B"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01783411","volume":"15","author":"S. Holm","year":"1993","unstructured":"S. Holm, M.M. Sorensen, The optimal graph partitioning problem, OR Spektrum 15 (1993) 1\u20138.","journal-title":"OR Spektrum"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1287\/opre.37.6.865","volume":"37","author":"D.S. Johnson","year":"1989","unstructured":"D.S. Johnson, C.R. Aragon, L.A. McGeoch, C. Schevon, Optimization by simulated annealing: an experimental evaluation: Part I, Graph partitioning, Operations Research 37 (1989) 865\u2013892.","journal-title":"Operations Research"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01585164","volume":"62","author":"E. Johnson","year":"1993","unstructured":"E. Johnson, A. Mehrotra, G.L. Nemhauser, Min-cut clustering, Mathematical Programming 62 (1993) 133\u2013152.","journal-title":"Mathematical Programming"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF01582072","volume":"63","author":"M. J\u00fcnger","year":"1994","unstructured":"M. J\u00fcnger, A. Martin, G. Reinelt, R. Weismantel, Quadratic 0\/1 optimization and a decomposition approach for the placement of electronic circuits, Mathematical Programming 63 (1994) 257\u2013279.","journal-title":"Mathematical Programming"},{"issue":"2","key":"CR16","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","volume":"49","author":"W. Kernighan","year":"1970","unstructured":"W. Kernighan, S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Systems Technical Journal 49 (2) (1970) 291\u2013307.","journal-title":"Bell Systems Technical Journal"},{"key":"CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"T. Lengauer","year":"1990","unstructured":"T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, Wiley, New York, 1990."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M.W. Padberg","year":"1991","unstructured":"M.W. Padberg, G. Rinaldi, A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review 33 (1991) 60\u2013100.","journal-title":"SIAM Review"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"1539","DOI":"10.1002\/nme.1620171008","volume":"17","author":"H.L.G. Pina","year":"1981","unstructured":"H.L.G. Pina, An algorithm for frontwidth reduction, International Journal on Numerical Methods in Engineering 17 (1981) 1539\u20131546.","journal-title":"International Journal on Numerical Methods in Engineering"},{"key":"CR20","volume-title":"The graph equipartition problem: optimal solutions, extensions and applications","author":"C.C. Souza de","year":"1993","unstructured":"C.C. de Souza, The graph equipartition problem: optimal solutions, extensions and applications, Doctoral Thesis, Facult\u00e9 des Sciences Appliqu\u00e9es, Universit\u00e9 Catholique de Louvain, Louvain-la-Neuve, Belgium, 1993."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/0045-7825(94)90137-6","volume":"111","author":"C.C. Souza de","year":"1994","unstructured":"C.C. de Souza, R. Keunings, L.A. Wolsey, O. Zone, A new approach to minimising the frontwidth in finite element calculations, Computer Methods in Applied Mechanics and Engineering 111 (1994) 323\u2013334.","journal-title":"Computer Methods in Applied Mechanics and Engineering"},{"key":"CR22","volume-title":"Decomposition and column generation for integer programs","author":"F. Vanderbeck","year":"1994","unstructured":"F. Vanderbeck, Decomposition and column generation for integer programs, Doctoral Thesis, Facult\u00e9 des Sciences Appliqu\u00e9es, Universit\u00e9 Catholique de Louvain, Louvain-la-Neuve, Belgium, 1994."},{"key":"CR23","volume-title":"Plazieren von Zellen: Theorie and L\u00f6sung eines quadratischen 0\u20131 Optimierungs-problem","author":"R. Weismantel","year":"1992","unstructured":"R. Weismantel, Plazieren von Zellen: Theorie and L\u00f6sung eines quadratischen 0\u20131 Optimierungs-problem, Dissertation, Technische Universit\u00e4t, Berlin, 1992."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581107.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01581107\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01581107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T03:54:40Z","timestamp":1586231680000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01581107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,4]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,4]]}},"alternative-id":["BF01581107"],"URL":"https:\/\/doi.org\/10.1007\/bf01581107","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,4]]}}}