Maximum Stable Set (MSS) problem is a well-known problem in graph theory. It is an NP-hard problem in general graphs and it has been extensively studied due to both its theoretical and practical importance. On the other hand, when MSS problem is limited to a class of graphs, called perfect graphs, it is polynomially solvable through a Semidefinite programming (SDP)-based algorithm. However, SDP solvers are known to be slow especially in larger problems, leading us to question the efficiency of the SDP-based algorithms. Moreover, there has been only limited number of studies examining the MSS problem solely in perfect graphs. Motivated by these, in this thesis, our objective is to compare performances of different algorithms with the SDP-based algorithm in perfect graphs. With this objective, we develop cutting plane algorithms that can solve MSS problem in perfect graphs. Additionally, investigate an existing branch-and-bound algorithm to see the performance of a powerful algorithm designed for MSS problem in general graphs. Then, we compare SDP-based algorithm with this branch-and-bound and our cutting plane algorithms using a number of perfect graph instances. Our comparison shows that the cutting plane algorithms perform considerably better than the other algorithms.

En büyük kararlı küme problemi çizgeler kuramındaki iyi bilinen bir problemdir. Bu problem genel bir çizge için NP-zor bir problemdir. Teorik ve uygulamadaki öneminden dolayı fazlaca çalışılmıştır. Problemi sadece çizge sınıflarının en önemli sınıflarından biri olan mükemmel çizgeler için ele aldığımız zaman, problemin polinom zamanda yarı kesin programlamaya dayanan bir algoritma ile çözüldüğünü görürüz. Fakat yarı kesin programlama problemlerinin özellikle fazla değişkenli oldu-ğunda yavaş çözüldüğü de bilinir. Ayrıca, problemi sadece mükemmel çizgelerde inceleyen sınırlı sayıda yayın vardır. Tüm bunları göz önüne aldığımızda bizim amacımız yarı kesin programlamaya dayanan algoritma ile diğer algoritmaların performansını mükemmel çizgelerde karşılaştırmaktır. Bu amaçla biz kesen düzlem algoritmaları geliştirdik. Ayrıca, en büyük kararlı küme problemini herhangi bir çizgede çözen güçlü bir algoritma örneği görebilmek için güçlü bir dal-sınır algoritmasını inceledik ve sonra bu algoritmaları mükemmel çizge örnekleri kullanarak karşılaştırdık. Karşılaştırmaları-mız kesen düzlem algoritmalarının diğerlerinden daha iyi çalıştığını ortaya çıkardı.