Réductions et conditions d'optimalité dans le problème de l'ensemble stable de poids maximal

Alain Billionnet

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

  • Volume: 15, Issue: 3, page 213-231
  • ISSN: 0399-0559

How to cite

top

Billionnet, Alain. "Réductions et conditions d'optimalité dans le problème de l'ensemble stable de poids maximal." RAIRO - Operations Research - Recherche Opérationnelle 15.3 (1981): 213-231. <http://eudml.org/doc/104786>.

@article{Billionnet1981,
author = {Billionnet, Alain},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {maximum weighted stable set; flow in a bipartite graph; optimality conditions; reduction},
language = {fre},
number = {3},
pages = {213-231},
publisher = {EDP-Sciences},
title = {Réductions et conditions d'optimalité dans le problème de l'ensemble stable de poids maximal},
url = {http://eudml.org/doc/104786},
volume = {15},
year = {1981},
}

TY - JOUR
AU - Billionnet, Alain
TI - Réductions et conditions d'optimalité dans le problème de l'ensemble stable de poids maximal
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1981
PB - EDP-Sciences
VL - 15
IS - 3
SP - 213
EP - 231
LA - fre
KW - maximum weighted stable set; flow in a bipartite graph; optimality conditions; reduction
UR - http://eudml.org/doc/104786
ER -

References

top
  1. 1. C. BERGE, Graphes et Hypergraphes, Dunod, Paris, 1970 Zbl0213.25702MR357173
  2. 2. A. BILLIONNET, Un algorithme pour le problème de l'ensemble stable de cardinal maximal, Communication au dixième symposium international de programmation mathématique, Montréal, 27-31 août 1979. 
  3. 3. L. BUTZ, P.L. HAMMER et D. HAUSMANN, Reduction Methods for the Vertex Packing problem, Research Report n° 7540-OR, Institut für okonometrie und operations research, Universitat Bonn, novembre 1975. Zbl0588.05020
  4. 4. P. L. HAMMER, P. HANSEN et B. SIMEONE, On Vertices Belonging to All and to no Maximum Stable Sets o f a Graph, F.U.C.A.M. Research, Report, 1980. Zbl0496.90056
  5. 5. I. Caradot et C. POTIEZ, Réalisation d'algorithmes efficaces en programmation linéaire en variables bivalentes, Mémoire d'Ingénieur de l'Institut d'Informatique d'Entreprise, 1979-1980, Paris. 
  6. 6. G. DEMOUCRON, Ensemble stable intérieurement d'un graphe. Gestion, , juillet-août 1968, p. 508 à 519. 
  7. 7. L. R. FORD et D. R. FULKERSON, Flots dans les graphes, Gauthier-Villars, Paris, 1966 Zbl0183.23601
  8. 8. M. R. GAREY et D. S. JOHNSON, Computers and Intractability, a Guide to the Theory of NP-Completeness, chap. 3, V. H. Freeman and Company, San Francisco, 1979. Zbl0411.68039MR519066
  9. 9. M. R. GAREY, D. S. JOHNSON et L. STOCKMEYER, Some Simplified NP-Complete Graph Problems, Theor. Comput Sc, vol. 1, 1976, p. 237-267. Zbl0338.05120MR411240
  10. 10. M. GROTSCHEL, L. LOVASZ et A. SCHRIJVER, Method and Its Consequences in Combinatorial Optimisation, Research Report n° 80151-OR, Instifür okonometrie und operations research, Universitat Bonn, 1980. Zbl0539.90078
  11. 11. P. HANSEN, Bornes et algorithmes pour les stables d'un graphe, Communication au colloque : « Regards sur la théorie des graphes », Cerisy, Manche, juin 1980. 
  12. 12. P. HANSEN, Upper Bounds for the Stability Number of a graph., Revue roumaine de Math, pures et appl., vol, 24, 1979, p. 1195-1199. Zbl0426.05032MR551969
  13. 13. D. J. HOUCK et R. R. VEMUGANTI, An Algorithm for the Vertex Packing Problem, Operations Research, vol. 25, n° 5, septembre-octobre 1977, p. 773 à 787. Zbl0383.90101MR444517
  14. 14. R. M. KARP, Reducibility Among Combinatorial Problems, dans R, E. MILLER et J. W. THATCHER, éd., Complexity of Computer Computations, New York, Plenum Press, 1972, p. 85-103. Zbl0366.68041MR378476
  15. 15. G. MINTY, On Maximal Independent Sets of Vertices in Claw-Free Graphs, Journal of Combinatorial Theory, B, vol. 28, n° 3, juin 1980, p. 284 à 304. Zbl0434.05043MR579076
  16. 16. G. L. NEMHAUSER et L. E. TROTTER, Vertex Packings : Structural Properties and Algorithms, Math. Programming, vol. 8, 1975, p. 232 à 248. Zbl0314.90059MR366738
  17. 17. J. C. PICARD et M. QUEYRANNE, On the Integer Valued Variables in the Linear Vertex Packing Problem, Math. Programming, vol 15, 1977, p, 97-101. Zbl0362.90065MR469268
  18. 18. N. SBIHI, Algorithme de recherche d'un stable de cardinalité maximal dans un graphe sans étoile, Rapport de Recherche. n° 103, Université scientifique et médicale de Grenoble, décembre 1977. Zbl0444.05049
  19. 19. R. E. TARJAN et A. E. TROJANOWSKI, Finding a Maximum Independent Set, S.I.A.M J. Computing, vol 6, 1977, p. 537-546. Zbl0357.68035MR463035

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.