The maximum stable set problem in perfect graphs
Mükemmel çizgelerde en büyük kararlı küme problemi
- Tez No: 474356
- Danışmanlar: DOÇ. TINAZ EKİM AŞICI
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 79
Özet
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ı.
Özet (Çeviri)
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.
Benzer Tezler
- İnsansız hava aracı için bir borda bilgisayarının mimarisi ve tasarımı
Başlık çevirisi yok
SAİT N. YURT
Yüksek Lisans
Türkçe
1995
Astronomi ve Uzay Bilimleriİstanbul Teknik ÜniversitesiY.DOÇ.DR. T. BERAT KARYOT
- Çelik ve alüminyum alaşımlı çekirdekli burkulması önlenmiş çaprazların (BÖÇ) tasarımı, üretimi ve yön değiştiren tekrarlı yükler etkisindeki davranışı
Design, fabrication, and cyclic behavior of steel and aluminum alloy core buckling restrained braces (BRBs)
ÇİGDEM KARATAŞ
Doktora
Türkçe
2012
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. OĞUZ CEM ÇELİK
- Türk sigorta sektörünün piyasa yapısı ve analizi
Market structure and anaysis of Turkish insurance sector
LÜTFİ AYKAÇ
- Yarı ergimiş tuz yöntemi ile kromit konsantresinden sodyum kromat üretimi
Production of sodium chromate from chromite ore via the sub-molten salt method
ECE TUNÇYÜREK
Yüksek Lisans
Türkçe
2023
Metalurji Mühendisliğiİstanbul Teknik ÜniversitesiMetalurji ve Malzeme Mühendisliği Ana Bilim Dalı
PROF. DR. SERVET İBRAHİM TİMUR
- Peptit bağlı altın nanoparçacıklar kullanarak bazı eser elementlerin ayrılması
Separation of some trace elements using peptide bound gold nanoparticles
GİZEM GEDİK
Yüksek Lisans
Türkçe
2013
Kimyaİstanbul Teknik ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. SÜLEYMAN AKMAN