User menu

The node capacitated graph partitioning problem: a computational study

Bibliographic reference Ferreira, Carlos ; Martin, Alexander ; De Souza, Cid ; Weismantel, Robert ; Wolsey, Laurence. The node capacitated graph partitioning problem: a computational study. In: Mathematical Programming, Vol. 81, no. 2, p. 229-256 (1998)
Permanent URL
  1. D. Applegate, R.E. Bixby, V. Chvátal, W. Cook, Finding cuts in the TSP, DIMACS Technical Report, 1994, pp. 95–05.
  2. F. Barahona, A. Casari, On the magnetisation of the ground states in two dimensional Ising spin glasses, Computer Physics Communications 49 (1988) 417–421.
  3. F. Barahona, M. Grötschel, M. Jünger, G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design, Operations Research 36 (1988) 493–513.
  4. F. Barahona, A. Mahjoub, On the cut polytope, Mathematical Programming 36 (1986) 157–173.
  5. N. Boissin, Optimisation des Fonctions Quadratiques en Variables Bivalentes, Thèse de Doctorat, Conservatoire National des Arts et Métiers, Paris, 1994.
  6. 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.
  7. S. Chopra, M.R. Rao, On the multiway cut polyhedron, Networks 21 (1991) 51–89.
  8. 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–267.
  9. C.E. Ferreira, A. Martin, R. Weismantel, A cutting plane based algorithm for the multiple knapsack problem, SIAM J. on Optimization 6 (1996) 858–877.
  10. 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–181.
  11. M. Grötschel, Y. Wakbayashi, A cutting plane algorithm for a clustering problem, Mathematical Programming Series B 45 (1989) 59–96.
  12. S. Holm, M.M. Sorensen, The optimal graph partitioning problem, OR Spektrum 15 (1993) 1–8.
  13. 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–892.
  14. E. Johnson, A. Mehrotra, G.L. Nemhauser, Min-cut clustering, Mathematical Programming 62 (1993) 133–152.
  15. M. Jünger, 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–279.
  16. Kernighan B. W., Lin S., An Efficient Heuristic Procedure for Partitioning Graphs, 10.1002/j.1538-7305.1970.tb01770.x
  17. T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, Wiley, New York, 1990.
  18. 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–100.
  19. H.L.G. Pina, An algorithm for frontwidth reduction, International Journal on Numerical Methods in Engineering 17 (1981) 1539–1546.
  20. C.C. de Souza, The graph equipartition problem: optimal solutions, extensions and applications, Doctoral Thesis, Faculté des Sciences Appliquées, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1993.
  21. 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–334.
  22. F. Vanderbeck, Decomposition and column generation for integer programs, Doctoral Thesis, Faculté des Sciences Appliquées, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1994.
  23. R. Weismantel, Plazieren von Zellen: Theorie and Lösung eines quadratischen 0–1 Optimierungs-problem, Dissertation, Technische Universität, Berlin, 1992.