An algorithm for the maximum internally stable set in a weighted graph

References

• Aho , A. V. , Hopcroft , J. E. and Ulman , J. D. 1974 . The Design and Analysis of Computer Algorithms , Addison-Wesley .
   Google Scholar
• Burlet M. Uhry J. P. Parity graphs. Mathematiques appliqués et informatique Rapport de Recherche No. 232, Université Scientifique et Médicale et Institut, National Polytechnique de Grenoble 1981
   Google Scholar
• Chvátal , V. 1977 . Determining the stability number of a graph . SIAM on Computing , 6 : 643 – 662 .
   Web of Science ®Google Scholar
• Cook , S. Proceedings of the Third ACM Symposium on the Theory of Computing . The complexity of theorem-proving procedures . pp. 151 – 158 . New York : Association for Computing Machinery .
   Google Scholar
• Ford , G. W. and Fulkerson , D. R. 1962 . Flows in Networks , Princeton, N. J : Princeton University Press .
   Google Scholar
• Fulkerson , D. R. 1972 . Anti-blocking polyhedra . Journal of Combinatorial Theory , 12 : 50 – 71 .
   Google Scholar
• Hansen , P. 1980 . “ Bornes et algorithmes pour les stables d’un graphe ” . In Regards sur la Theorie des Graphes Edited by: Hansen , P. and De Werra , D. 38 – 53 . Presses Polytechniques Romandes
   Google Scholar
• Hsu , W. , Ikura , Y. and Nemhauser , G. L. 1981 . A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles . Mathematical Programming , 20 : 225 – 232 .
   Web of Science ®Google Scholar
• Garey , M. R. and Johnson , D. S. 1979 . “ Computers and intractability ” . In A Guide to the Theory of NP-Completeness , Freeman .
   Google Scholar
• Garey , M. R. , Johnson , D. S. and Stockmeyer , L. 1976 . Some simplified NP-complete graph problems . Theoretical Computer Science , 1 : 237 – 267 .
   Google Scholar
• Garvil , F. 1972 . Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph . SIAM on Computing , 1 : 180 – 187 .
   Google Scholar
• Garvil , F. 1975 . Algorithms on circular-arc graphs . Networks , 4 : 357 – 369 .
   Google Scholar
• Grötschel M. Lovasz L. Schrijver A. The Ellipsoid Method and its Consequences in Combinatorial Optimization W. P. 80151-OR Institut für Ökonometrie und Operations Research Universität Bonn 1980
   Google Scholar
• Karp , R. 1972 . “ Reducibility among combinatorial problems ” . In Complexity of Computer Computations , Edited by: Miller , R. E. M. and Thatcher , J. W. 85 – 104 . New York : Plenum Press .
   Google Scholar
• Khachiyan (Hacijan) L. G. A polynomial algorithm for linear programming Translated as Soviet Mathematics Doklady 20 191 194 Doklady 244 No. 5
   Google Scholar
• Loukakis , E. 1980 . A recursive algorithm for the maximum cardinality independent set . Bulletin of the Greek Mathematical Society , 21 : 87 – 110 .
   Google Scholar
• Loukakis , E. and Tsouros , C. 1981 . Determining the number of internal stability of a graph . International Journal of Computer Mathematics , 11 : 207 – 220 .
   Web of Science ®Google Scholar
• Loukakis , E. and Tsouros , C. 1981 . A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically . Computing , 27 : 349 – 366 .
   Web of Science ®Google Scholar
• Minty , G. J. 1980 . On maximal independent sets of vertices in claw-free graphs . Journal of Combinatorial Theory , (B) 28 : 284 – 304 .
   Web of Science ®Google Scholar
• Rotem , D. and Urrutia , J. 1981 . Finding maximum cliques in circle graphs . Networks , 11 : 269 – 278 .
   Web of Science ®Google Scholar
• Tarjan , R. E. and Trojanowski , A. E. 1977 . Finding a maximum independent set . SIAM on Computing , 6 : 537 – 546 .
   Google Scholar