A decomposition approach to solve the selective graph coloring problem
Seçmeli çizge boyama problemi için bir ayrıştırma yaklaşımı
- Tez No: 540510
- Danışmanlar: DOÇ. DR. TINAZ EKİM AŞICI, PROF. DR. ZEKİ CANER TAŞKIN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- 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ı: 154
Özet
Çizge boyama problemi, bir çizgedeki tüm köşeleri birbirine komşu iki köşe aynı rengi almayacak şekilde boyama problemidir. Seçmeli çizge boyama problemi ise bilinen çizge boyama probleminin genelleştirilmiş bir hâlidir; bir çizge ve onun köşelerinin oluşturduğu kümenin bir bölmelemesi verilmişken, her bölmeden yalnızca bir tane köşeyi, sonuçta gerekecek renk sayısı en az olacak şekilde seçme problemidir. Bu çalışma, seçmeli çizge boyama problemi için ayrıştırmaya dayalı bir çözüm yöntemini, önce birtakım özel çizge sınıflarına ve daha sonra da belirli bir yapıya sahip olmayan genel çizgelere uygulamayı amaçlamaktadır. Çalışmanın ele aldığı özel çizge sınıfları, kusursuz çizge sınıfı ve onun devşirim çizgeleri, genelleştirilmiş iki parçalı çizgeler ve ki-rişli çizgelerden oluşan özel altsınıflarıdır. Kullanılan ayrıştırma yönteminin başarımını sınayabilmek için bu çizge sınıflarından somut örneklere duyulan gereksinim, çalışmanın ikinci kısmının ele alınan çizge sınıflarından rastgele örnek üretmek için yöntemler geliştirmeye odaklanmasını sağlamıştır. Ardından, ayrıştırma yöntemi, çalışmanın i-kinci kısmında üretilen farklı boyut ve yoğunluktaki çizge örnekleri üzerinde sınanmış ve sonuçlar, bir tamsayı programlama modelinin CPLEX ile çözdürülmesinden ve li-teratürde bilinen en iyi yöntemden elde edilen sonuçlarla karşılaştırılmıştır. Yapılan deneylerin sonucu göstermiştir ki ayrıştırma yöntemimiz, çözüm bulmadaki başarımı, devşirim ve genelleştirilmiş iki parçalı çizge sınıflarında özellikle düşük yoğunluklu çizgelerde, kirişli çizgelerde ise yoğunluktan bağımsız olarak önemli ölçüde geliştirmiştir. Kusursuz çizgelerin genel biçiminde yapılan deneylerde ise ayrıştırma yönteminin, karşılaştırma yapılan diğer iki yönteme de genel olarak üstün sonuçlar sağladığı görülmüştür. Öte yandan, genel çizgelerde, ayrıştırma yönteminin karşılaştırılan yöntemlerle rekabet edebilir hale gelmesi için daha fazla geliştirilmesi gerektiği görülmüştür.
Özet (Çeviri)
Graph coloring is the problem of assigning a minimum number of colors to all vertices of a graph such that no two vertices that are linked by an edge receive the same color. The selective graph coloring problem is a generalization of the standard graph coloring problem; given a graph with a partition of its vertex set into clusters, the aim is to pick exactly one vertex per cluster so that, among all possible selections, the number of colors needed to color the vertices in the selection is minimum. In this study, we focus on a decomposition based exact solution framework for selective coloring, and apply it first to some special graph families, and then to general graphs with no particular structure. The special classes of graphs that we consider are perfect graphs and some special subclasses of perfect graphs, which are permutation, generalized split, and chordal graphs. In order to test the performance of our solution approach, we need graph instances from these graph classes, which led us to concentrate on the generation of random graphs from the graph classes under consideration in the second part of this study. We then test the decomposition method on graphs with different sizes and densities that we have produced with our generation methods, present computational results and compare them with an integer programming formulation of the problem solved by CPLEX, and a state-of-the-art algorithm from the literature. Our computational experiments indicate that our decomposition approach significantly improves the solution performance, especially in low-density graphs in permutation and generalized split graphs, and regardless of the edge-density in the class of chordal graphs. For perfect graphs in their general form, our approach outperforms both of the other two methods. In the case of general graphs, however, further improvements are needed to make our method competitive with the alternative methods we compare with.
Benzer Tezler
- Sahada programlanabilir kapı dizileri ile lojik devre tasarımı
Başlık çevirisi yok
VOLKAN SEZER
Yüksek Lisans
Türkçe
1996
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. AHMET DERVİŞOĞLU
- Benzin motorlarında indirgenmiş kinetik model uygulaması
Reduced chemical kinetic model application to spark ignition engines
CÜNEYT UYKUR
- Gemilerde kullanılan seçici katalitik indirgeme sistemlerinde tortu oluşumunun ve azot oksit indirgeme performanslarının deneysel ve sayısal olarak incelenmesi
Experimental and numerical investigation of urea-deposit formation and nitrogen oxide reduction performances in selective catalytic reduction systems used on marine vessels
TALAT GÖKÇER CANYURT
Doktora
Türkçe
2023
Gemi Mühendisliğiİstanbul Teknik ÜniversitesiGemi İnşaatı ve Gemi Makineleri Mühendisliği Ana Bilim Dalı
PROF. DR. SELMA ERGİN
- Hierarchical reinforcement learning in complex wargame environments
Kompleks savaş oyunu ortamlarında hiyerarşik pekiştirmeli öğrenme
KUBİLAY KAĞAN KÖMÜRCÜ
Yüksek Lisans
İngilizce
2024
Astronomi ve Uzay Bilimleriİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DOÇ. DR. NAZIM KEMAL ÜRE
- Uncapacitated multiple allocation hub location problem under congestion
Trafik sıkışıklığı altında çok atamalı kapasite kısıtsız ana dağıtım üssü yerleşim problemi
ÇAĞRI ÖZGÜN KİBİROĞLU
Doktora
İngilizce
2019
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. YUSUF İLKER TOPCU