An algorithm for finding a maximum weighted independent set in an arbitrary graph

References

• Balas , E. , Chvatal , V. and Nesetril , J. 1987 . On the maximum weight clique problem . Math. of Oper. Research , 12 ( 3 ) : 522 – 535 .
   Web of Science ®Google Scholar
• Balas , E. and Yu , C. S. 1986 . Finding the maximum clique in an arbitrary graph . SIAM J. Comput. , 15 ( 4 ) : 1054 – 1068 .
   Web of Science ®Google Scholar
• Bron , C. and Kerbosch , J. 1973 . Finding all cliques of an undirected graph . Comm. ACM , 16 ( 6 ) : 575 – 577 .
   Web of Science ®Google Scholar
• Carraghan R. Pardalos P. M. An exact algorithm for the maximum clique problem Operations Research Letters 1990 To appear
   Web of Science ®Google Scholar
• Friden C. Hertz A. de Werra D. TABARIS: An exact algorithm based on Tabu search for finding a maximum independent set in a graph Dep. de Math. 1989 Technical Report ORWP 89/03, Ecole Pol. Fed. de Lausanne
   Google Scholar
• Garey , M. R. and Johnson , D. S. 1979 . Computers and Intractability, A Guide to the Theory of NP-Completeness , W. H. Freeman and Company .
   Google Scholar
• Gavril , F. 1973 . Algorithms for a maximum clique and maximum independent set of a circle graph . Networks , 3 : 261 – 273 .
   Google Scholar
• Gendreau , M. , Picard , J.-C. and Zubieta , L. 1988 . “ An efficient implicit enumeration algorithm for the maximum clique problem ” . In Lecture Notes in Economics and Mathematical Systems 304 , 79 – 91 . Springer-Verlag .
   Google Scholar
• Gerhards , L. and Lindenberg , W. 1979 . Clique detection for nondirected graphs: Two new algorithms . Computing , 21 : 295 – 322 .
   Web of Science ®Google Scholar
• Grötschel , M. , Lovasz , L. and Schrijver , A. 1988 . Geometric Algorithms and Combinatorial Optimization , Springer-Verlag .
   Google Scholar
• Hsu , W. L. , Ikura , Y. and Nemhauser , G. L. 1981 . A polynomial algorithm for maximum weighted vertex packings in graphs without long odd cycles . Math. Programming , 20 : 225 – 232 .
   Web of Science ®Google Scholar
• Kopf , R. and Ruhe , G. 1987 . A computational study of the weighted independent set problem for general graphs . Foundations of Control Engineering , : 167 – 180 .
   Google Scholar
• Loukakis , E. and Tsouros , C. 1982 . Determining the number of internal stability of a graph . Intern. J. Computer Math. , 11 : 232 – 248 .
   Web of Science ®Google Scholar
• Pardalos , P. M. and Phillips , A. T. 1990 . A global optimization approach for solving the maximum clique problem . Inter. J. Computer Mathematics , 33 : 209 – 216 .
   Web of Science ®Google Scholar
• Pardalos P. M. Rodgers G. P. A branch and bound algorithm for the maximum clique problem. Technical Report Computer Science Department, The Pennsylvania State University
   Google Scholar
• Pardalos , P. M. and Rodgers , G. P. 1990 . Computational aspects of a branch and bound algorithm for quadratic 0–1 programming . Computing , 45 : 131 – 144 .
   Web of Science ®Google Scholar
• Pardalos , P. M. and Rodgers , G. P. 1989 . “ Parallel branch and bound algorithms for unconstrained quadratic zero-one programming ” . In Impact of Recent Computer Advances on Operations Research , 131 – 143 . North-Holland .
   Google Scholar
• Pardalos , P. M. and Rodgers , G. P. 1990 . Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture . Annals of Operations Research , 22 : 271 – 292 .
   Google Scholar
• Tarjan , R. E. and Trojanowski , A. E. 1977 . Finding a maximum independent set . SIAM J. Comput. , 6 ( 3 ) : 537 – 546 .
   Google Scholar
• Tsukiyama , S. , Ide , M. , Ariyoshi , H. and Shirakawa , I. 1977 . A new algorithm for generating all the maximimal independent sets . SIAM J. Comput. , 6 : 505 – 517 .
   Google Scholar