Problème de la bipartition minimale d'un graphe

Catherine Roucairol; Pierre Hansen

RAIRO - Operations Research - Recherche Opérationnelle (1987)

  • Volume: 21, Issue: 4, page 325-348
  • ISSN: 0399-0559

How to cite

top

Roucairol, Catherine, and Hansen, Pierre. "Problème de la bipartition minimale d'un graphe." RAIRO - Operations Research - Recherche Opérationnelle 21.4 (1987): 325-348. <http://eudml.org/doc/104927>.

@article{Roucairol1987,
author = {Roucairol, Catherine, Hansen, Pierre},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {minimal bipartitioning; minimal cut; arc-weighted graph; lower bound; Lagrangian relaxation; maximum flow; branch-and-bound},
language = {fre},
number = {4},
pages = {325-348},
publisher = {EDP-Sciences},
title = {Problème de la bipartition minimale d'un graphe},
url = {http://eudml.org/doc/104927},
volume = {21},
year = {1987},
}

TY - JOUR
AU - Roucairol, Catherine
AU - Hansen, Pierre
TI - Problème de la bipartition minimale d'un graphe
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1987
PB - EDP-Sciences
VL - 21
IS - 4
SP - 325
EP - 348
LA - fre
KW - minimal bipartitioning; minimal cut; arc-weighted graph; lower bound; Lagrangian relaxation; maximum flow; branch-and-bound
UR - http://eudml.org/doc/104927
ER -

References

top
  1. 1. E. R. BARNES, An Algorithm for Partitioning the Notes of a Graph, S.I.A.M. J. Alg. Disc. Meth., vol., n° 4, 1982, p. 541-550. Zbl0505.05050MR679649
  2. 2. P. CHAILLOU, P. HANSEN et Y. MAHIEU, Best Network Flow Bounds for the Quadratic Knapsack Problem, Presented at NETFLOW 83 International Workshop, Pisa, Italy, 1983. Zbl0678.90061
  3. 3. N. CHRISTOFIDÈS et P. BROOKER, The Optimal Partitioning of Graphs, S.I.A.M. J. Apl. Math., vol. 30, n° 1, 1976, p. 55-70. Zbl0321.05123MR405911
  4. 4. M. GAREY, E. JOHNSON et STOCKMEYER, Some Simplified NP-Complete Problems, Theoretical Computer Science, vol. 1, 1976, p. 237-267. Zbl0338.05120MR411240
  5. 5. P.L. HAMMER (Ivanescu), Some Network Flow Problems Solved by Pseudo-Boolean Programming, Operations Research, vol. 13, 1965, p. 388-299. Zbl0132.13804MR184728
  6. 6. A. V. KARZANOV, Determining the Maximal Flow in at Network by the Method of Preflows, Soviet. Math. Dokl., vol. 15, 1974, p. 434-437. Zbl0303.90014
  7. 7. M. MINOUXProgrammation Mathématique, t. 1, C.N.E.T., E.N.S.T., Dunod, Paris, 1983. Zbl0546.90056
  8. 8. V. M. MALHORTA, M. P. KUMAR et S. N. MAHESHWARI, An Algorithm for Finding Maximum Flow in Networks, Information Processing Letters, vol.7-6, 1978, p. 277-278. Zbl0391.90041MR509428
  9. 9. A. NIJENHUIS et H. S. WILF, Combinatorial Algorithms, Second Edition, Academic Press, New York, 1978. Zbl0343.68004MR510047
  10. 10. J. C. PICARD et M. QUEYRANNE, Networks, Graphs and Some Non Linear 0.1 Programming Problems, Tech. Rep. EP77-R-32, École Polytechnique de Montréal, Canada, , 1977. 
  11. 11. J. C. PICARD et H. D. RATLIFF, Minimum Cuts and Related Problems, Networks, vol. 5, 1975, p. 357-370. Zbl0325.90047MR391960
  12. 12. J. C. PICARD et H. D. RATLIFF, A Cut Approach to a Class of Quadratic Integer Programming Problems, Networks, vol. 10, 1980, p. 363-370. Zbl0452.90051MR597274
  13. 13. P. SIARRY, La méthode du Recuit Simulé : application à la conception de circuits électroniques, Thèse de Doctorat de l'Université Paris-VI, Spécialités : Sciences Physiques, Paris, novembre 1986. 

NotesEmbed ?

top

You must be logged in to post comments.