Lower bounds to the graph partitioning problem through generalized linear programming and network flows
RAIRO - Operations Research - Recherche Opérationnelle, Tome 21 (1987) no. 4, pp. 349-364. 
@article{RO_1987__21_4_349_0,
     author = {Minoux, M. and Pinson, E.},
     title = {Lower bounds to the graph partitioning problem through generalized linear programming and network flows},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {349--364},
     publisher = {EDP-Sciences},
     volume = {21},
     number = {4},
     year = {1987},
     mrnumber = {932184},
     zbl = {0657.90095},
     language = {en},
     url = {http://www.numdam.org/item/RO_1987__21_4_349_0/}
}
TY  - JOUR
AU  - Minoux, M.
AU  - Pinson, E.
TI  - Lower bounds to the graph partitioning problem through generalized linear programming and network flows
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1987
SP  - 349
EP  - 364
VL  - 21
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_1987__21_4_349_0/
LA  - en
ID  - RO_1987__21_4_349_0
ER  - 
%0 Journal Article
%A Minoux, M.
%A Pinson, E.
%T Lower bounds to the graph partitioning problem through generalized linear programming and network flows
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1987
%P 349-364
%V 21
%N 4
%I EDP-Sciences
%U http://www.numdam.org/item/RO_1987__21_4_349_0/
%G en
%F RO_1987__21_4_349_0
Minoux, M.; Pinson, E. Lower bounds to the graph partitioning problem through generalized linear programming and network flows. RAIRO - Operations Research - Recherche Opérationnelle, Tome 21 (1987) no. 4, pp. 349-364. http://www.numdam.org/item/RO_1987__21_4_349_0/

Barnes E. R., An Algorithm for Partitioning the Nodes of a Graph, SIAM J. Alg. Discr. Meth. Vol. 4, 1982, pp. 541-550. | MR | Zbl

Benders J. F., Partitioning Procedures for solving mixed variables programming problems, Numerische Mathematik, Vol. 4, 1962, pp. 238-252. | MR | Zbl

Christofides N. and Brooker P., The Optimal Partitioning of Graphs, SIAM J. Appl. Math. Vol. 30, No. 1, 1976, pp. 55-70. | MR | Zbl

Dantzig G. B. and Wolfe P., The Decomposition Algorithm for Linear Programming, Econometrica, Vol. 29, No. 4, 1961, pp. 767, 778. | MR | Zbl

Dinic E. A., Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation, Soviet Math. Dokl., Vol. 11, 1970, pp. 1277-1280. | Zbl

Hammer P. L., Hansen P. and Simeone B., Roof Duality, Complementation and Persistency in Quadratic 0-1 Optimization, Mathematical Programming, Vol. 28, 1984, pp. 121-155. | MR | Zbl

Hansen P. and Roucairol C., Problème de la bipartition minimale d'un graphe, RAIRO (à paraître). | Numdam | Zbl

Hyafil L. and Rivest R. L., Graph Partitioning and Constructing Optimal Decision Trees are Polynomial Complete Problems, Report n° 33, IRIA-Laboria, Rocquencourt, France, 1973.

Karzanov A. V., Determining the Maximal Flow in a Network by the Method of Preflows, Soviet Math. Dokl. Vol. 15, 1974, pp. 434-437. | Zbl

Lu S. M. and Williams A. C., Roof Duality for Nonlinear 0-1 Optimization, Rutcor Research Report, RRR 2-85, 1985.

Minoux M., Programmation Mathématique : théorie et algorithmes, Dunod, Paris, 1983 (English translation J. Wiley & Sons, 1986). | MR | Zbl

Minoux M. Optimal Traffic Assignaient in a SS/TDMS Frame: a New Approach by Set Covering and Column Generation, ORSA/TIMS meeting, Dallas, Texas, 1984, Appeared in RAIRO, Vol. 20, No. 4, 1986, pp. 1-13. | Numdam | Zbl

Minoux M., A Class of Combinatorial Problems with Polynomially Solvable Large Scale set Covering/Partitioning Relaxations, Journées du 20e anniversaire du Groupe Combinatoire de l'AFCET, Paris-3, 5 décembre 1986, appeared in RAIRO, Vol. 21, No. 2, 1987, pp. 105-136. | EuDML | Numdam | MR | Zbl

Rhys J. M. W., A Selection Problem of Shared Fixed Costs and Network Flows, Management Science, Vol. 17, No. 3 (1970), pp. 200-207. | MR | Zbl

Ribeiro C., Minoux M. et Penna C., A Combined Branch and Bound/Column generation Approach to very large Scale Set Covering Problems with Special Structure, ORSA/-TIMS meeting, Miami, Florida, November 1986, (to appear). | MR

Rosenberg I. G., Reduction of Bivalent Maximization to the Quadratic Case, Cahiers du Centre d'Études de Recherche Opérationnelle, Vol. 17, 1975, pp.71-79. | MR | Zbl

Tarjan R. E., A Simple Version of Karzanov's Blocking Flow Algorithm, Operations Research Letters, Vol. 2, No. 6 (1984), pp. 265-268. | MR | Zbl

Willams A. C., Quadratic 0-1 Programming Using the roof Dual with Computational Results, RUTCOR Research Report RRR8-85, 1985.