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

Free Access

Issue		RAIRO-Oper. Res. Volume 15, Number 3, 1981


Page(s)		213 - 231
DOI		https://doi.org/10.1051/ro/1981150302131
Published online		06 February 2017

1. C. BERGE, Graphes et Hypergraphes, Dunod, Paris, 1970 [MR: 357173] [Zbl: 0213.25702] [Google Scholar]
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. [Google Scholar]
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: 0588.05020] [Google Scholar]
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: 0496.90056] [Google Scholar]
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. [Google Scholar]
6. G. DEMOUCRON, Ensemble stable intérieurement d'un graphe. Gestion, , juillet-août 1968, p. 508 à 519. [Google Scholar]
7. L. R. FORD et D. R. FULKERSON, Flots dans les graphes, Gauthier-Villars, Paris, 1966 [Zbl: 0183.23601] [Google Scholar]
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: 519066] [Zbl: 0411.68039] [Google Scholar]
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: 411240] [Zbl: 0338.05120] [Google Scholar]
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. [Zbl: 0539.90078] [Google Scholar]
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. [Google Scholar]
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: 551969] [Zbl: 0426.05032] [Google Scholar]
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: 444517] [Zbl: 0383.90101] [Google Scholar]
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: 378476] [Zbl: 0366.68041] [Google Scholar]
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: 579076] [Zbl: 0434.05043] [Google Scholar]
16. G. L. NEMHAUSER et L. E. TROTTER, Vertex Packings : Structural Properties and Algorithms, Math. Programming, vol. 8, 1975, p. 232 à 248. [MR: 366738] [Zbl: 0314.90059] [Google Scholar]
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: 469268] [Zbl: 0362.90065] [Google Scholar]
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: 0444.05049] [Google Scholar]
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: 463035] [Zbl: 0357.68035] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.