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

 Access to full text

 Full (PDF)

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

1. Ngoc C. Lê, Christoph Brause, Ingo Schiermeyer, Extending the MAX Algorithm for Maximum Independent Set
2. Alain Billionnet, Isabelle Caradot, Comparaison expérimentale d'algorithmes pour les problèmes de recouvrement et de maximisation d'une fonction pseudo-booléenne