The selective graph coloring problem
Seçmeli boyama problemi için sezgisel yöntemler
- Tez No: 325554
- Danışmanlar: YRD. 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: 2013
- 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ı: 143
Özet
Klasik çizge boyama problemi, verilen bir çizgenin köşelerinin iki komşu köşe aynı rengi almayacak şekilde en az renk kullanılarak boyanması problemidir. Bir çizgenin boyanabileceği en az sayıdaki renge, o çizgenin boyama sayısı denir. Klasik çizge boyama probleminin karar versiyonu NP-tam, optimizasyon versiyonu NP-zor'dur. Seçmeli boyama problemi, klasik boyama probleminin bir genellemesidir. Bu problemde, çizge ve bu çizgenin köşelerinin parçalanmış hali girdi olarak verilmektedir. Problemin amacı, iki komşu köşe aynı rengi almayacak şekilde her parçadan bir köşe seçilerek bu şekilde oluşan çizgeyi en az sayıda renkle boyamaktır. Seçmeli boyama problemi çeşitli uygulamaların çözümüne yardımcı olabilecektir. Doğal bir felaketten sonra yeni vericilere frekans atama probleminin çözülebilmesi için GSM ağının tamir edilmesi ya da yeniden kurulması ve her iş paketinin yapılabileceği belli zaman aralıklarının olduğu bir çizelgeleme probleminin çözülmesi bu uygulamalara örnektir. Sezgisel yöntemler, NP-zor problemler için hızlı çalışan ve en iyi sonuca yakın sonuçlar vermeyi amaçlayan yöntemlerdir. Bu nedenle seçmeli boyama probleminin çözümü için sezgisel yöntemlerin geliştirilmesi kaçınılmazdır. Tezin ana konusu seçmeli çizge boyama probleminin çözümü için yeni sezgisel ve tam çözüm yöntemleri geliştirilmesidir. Bu amaçla çeşitli sezgisel ve tam çözüm yöntemleri denenmiş ve deneylerle sonuçları incelenmiştir.
Özet (Çeviri)
In the classical graph coloring problem, the vertices of a given graph are colored such that no two adjacent vertices take the same color with the objective of coloring the whole graph with the minimum number of colors. The minimum number of colors that is needed to color a graph is called the chromatic number of the graph. It is known that the decision version of the problem is NP-complete and the optimization version of the problem is NP-hard. The selective graph coloring problem is a generalization of the classical graph coloring problem, where a graph and a partition of its vertices into different clusters are given as an input and the objective is assigning one color to one vertex in each cluster so that two adjacent vertices get different colors and the total number of colors is minimized. The selective graph coloring problem helps modeling and solving several real life problems. Rebuilding or repairing a cellular phone network after a disaster and allocating new frequencies to these transmitters and scheduling problems with selection among a fixed set of time windows for each task are examples of real life problems for which the selective graph coloring problem will be helpful. Such various applications and the intractable nature of the selective graph coloring problems made the usage of heuristic methods inevitable. The main subject of this thesis is developing new heuristic approaches and exact methods for the solution of the selective graph coloring problem. For this purpose, several heuristic approaches and exact methods have been tried on some graph classes and their efficiency is compared through experiments.
Benzer Tezler
- A decomposition approach to solve the selective graph coloring problem
Seçmeli çizge boyama problemi için bir ayrıştırma yaklaşımı
OYLUM ŞEKER
Doktora
İngilizce
2018
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. TINAZ EKİM AŞICI
PROF. DR. ZEKİ CANER TAŞKIN
- Gazlı aromalı içeceklerin iyon kromatografi-kondüktivite dedektörü ile anyon tayini
Anion determination of carbonated flavored beverages with ion chromatography - conductivity dedector
BÜŞRA İPEK
- Hyper-heuristics for grouping problems
Gruplama problemleri için çok hedefli üst buluşsallar
MURAT BİRBEN
Yüksek Lisans
İngilizce
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ENDER ÖZCAN
- Kopigmentasyon ile Hibiskus sabdariffa'dan stabil antosiyanin bazlı gıda renklendiricilerinin üretimi ve model gıdalara uygulanması
Production of stable anthocyanin based food colorants from Hibiscus sabdariffa by copigmentation and their application to model foods
VİLDAN EYİZ
Doktora
Türkçe
2024
Gıda MühendisliğiNecmettin Erbakan ÜniversitesiGıda Mühendisliği Ana Bilim Dalı
PROF. DR. SELMAN TÜRKER
DOÇ. DR. İSMAİL TONTUL
- Kozmetik ürünlerinde paraben tayini için kemometrik optimizasyona dayalı yeni analitik yöntem
New analytical method for the determination of paraben in cosmetic products based on chemometric optimization
AYŞENUR ÖZTÜRK ALTUNAY