Réductions et conditions d'optimalité dans le problème de l'ensemble stable de poids maximal
RAIRO - Operations Research - Recherche Opérationnelle, Tome 15 (1981) no. 3, pp. 213-231.
@article{RO_1981__15_3_213_0,
     author = {Billionnet, Alain},
     title = {R\'eductions et conditions d'optimalit\'e dans le probl\`eme de l'ensemble stable de poids maximal},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {213--231},
     publisher = {EDP-Sciences},
     volume = {15},
     number = {3},
     year = {1981},
     mrnumber = {637193},
     zbl = {0463.90041},
     language = {fr},
     url = {http://www.numdam.org/item/RO_1981__15_3_213_0/}
}
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
SP  - 213
EP  - 231
VL  - 15
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_1981__15_3_213_0/
LA  - fr
ID  - RO_1981__15_3_213_0
ER  - 
%0 Journal Article
%A Billionnet, Alain
%T Réductions et conditions d'optimalité dans le problème de l'ensemble stable de poids maximal
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1981
%P 213-231
%V 15
%N 3
%I EDP-Sciences
%U http://www.numdam.org/item/RO_1981__15_3_213_0/
%G fr
%F RO_1981__15_3_213_0
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, Tome 15 (1981) no. 3, pp. 213-231. http://www.numdam.org/item/RO_1981__15_3_213_0/

1. C. Berge, Graphes et Hypergraphes, Dunod, Paris, 1970 | MR | Zbl

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. 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. | Zbl

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. | Zbl

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. G. Demoucron, Ensemble stable intérieurement d'un graphe. Gestion, , juillet-août 1968, p. 508 à 519.

7. L. R. Ford et D. R. Fulkerson, Flots dans les graphes, Gauthier-Villars, Paris, 1966 | Zbl

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. | MR | Zbl

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. | MR | Zbl

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.

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. P. Hansen, Upper Bounds for the Stability Number of a graph., Revue roumaine de Math, pures et appl., vol, 24, 1979, p. 1195-1199. | MR | Zbl

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. | MR | Zbl

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. | MR | Zbl

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. | MR | Zbl

16. G. L. Nemhauser et L. E. Trotter, Vertex Packings : Structural Properties and Algorithms, Math. Programming, vol. 8, 1975, p. 232 à 248. | MR | Zbl

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. | MR | Zbl

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. | Zbl

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. | MR | Zbl