Arşiv ve Dokümantasyon Merkezi
Dijital Arşivi

The maximum stable set problem in perfect graphs

Basit öğe kaydını göster

dc.contributor Graduate Program in Industrial Engineering.
dc.contributor.advisor Aşıcı, Tınaz Ekim.
dc.contributor.author Düzgün, Ahmet Çağrı.
dc.date.accessioned 2023-03-16T10:29:11Z
dc.date.available 2023-03-16T10:29:11Z
dc.date.issued 2017.
dc.identifier.other IE 2017 D88
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/13372
dc.description.abstract 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 Semide nite programming (SDP)-based algorithm. However, SDP solvers are known to be slow especially in larger problems, leading us to question the e ciency 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 di erent 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.
dc.format.extent 30 cm.
dc.publisher Thesis (M.A.) - Bogazici University. Institute for Graduate Studies in the Social Sciences, 2017.
dc.subject.lcsh Graph theory.
dc.title The maximum stable set problem in perfect graphs
dc.format.pages ix, 70 leaves ;


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım