Computational complexity of list coloring and ıts variants for particular graph classes
Liste renklendirme probleminin ve varyantlarının belirli çizge sınıfları için hesaplama karmaşıklığı
- Tez No: 851410
- Danışmanlar: DR. ÖĞR. ÜYESİ ÖZNUR YAŞAR DİNER
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Bilim ve Teknoloji, Matematik, Computer Engineering and Computer Science and Control, Science and Technology, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: Türkçe
- Üniversite: Kadir Has Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 120
Özet
Her bir 𝑣 ∈ 𝑉 düğümü için bir 𝐺 = (𝑉, 𝐸) çizgesi ve her bir düğüme atanan mevcut renklerin bir listesi 𝐿(𝑣) verilmiştir. Burada Liste 3-Renklendirme problemi her düğümün 𝐿(𝑣) ⊆ {1, 2, . . . , 𝑘}, kendi listesinden bir renk aldığı ve 𝐺'deki hiçbir iki komşu düğümün aynı rengi alamadığı renk atama problemini ifade eder. Liste 3-Renklendirme probleminin karar versiyonu, iki parçalı çizgeler için NP-Tamdır ve tarak dışbükey iki parçalı çizgelerdeki karmaşıklığı açık bir problemdir. Bu tezde Liste 3-Renklendirme problemini tarak dışbükey iki parçalı çizgelerin süper sınıfı olan tırtıl dışbükey iki parçalı çizgelere indirgeyen polinom zamanlı bir algoritma veriyoruz. Tanıma algoritmaları verimli algoritmaların tasarlanmasında çok önemli bir yer tutar. İki parçalı çizgeler gibi birçok çizge sınıfını tanımak ve bir çizgenin uygun temsilini üretmek için iyi bilinen algoritmalar vardır. Burada tırtıl dış bükey iki parçalı çizge sınıfı için bir polinom zamanlı tanıma algoritması ve bu çizgeye karşılık gelen bir tırtıl temsili veriyoruz. Bu algoritma değiştirilerek, tarak dışbükey iki parçalı çizgelerin için bir polinom zamanlı tanıma algoritması verildi. Liste 3-Renklendirme ve tanıma algoritmalarının yanında Liste renklendirme probleminin bir uygulaması olan Futoshiki Problemi ile ilgileniyoruz. Futoshiki, bir NP-Tam Latin Kare Tamamlama Tipi Bulmacasıdır. Futoshiki bulmacasını bir koşul tatmin problemi olarak ele aldığımızda, öncelikle buna yönelik bir liste renklendirme tabanlı algoritma veriyoruz. Ayrıca, geliştirdiğimiz algoritmanın performansını gerçekleştirdiğimiz deneylerden elde ettiğimiz sonuçlarla karşılaştırmak için iki deterministik algoritma daha sunuyoruz. Son olarak, Minimum Çatışma Algoritması, Karınca Kolonisi Optimizasyon Algoritması ve Genetik Algoritmayı içeren üç stokastik algoritma veriyoruz.
Özet (Çeviri)
Given a graph 𝐺 = (𝑉, 𝐸) and a list of available colors 𝐿(𝑣) for each vertex 𝑣 ∈ 𝑉, where 𝐿(𝑣) ⊆ {1, 2, . . . , 𝑘}, List 𝑘-Coloring refers to the problem of assigning colors to the vertices of 𝐺 so that each vertex receives a color from its own list and no two neighboring vertices receive the same color. The decision version of the problem, List 3-Coloring, is NP-complete even for bipartite graphs, and its complexity on comb-convex bipartite graphs has been an open problem. In this thesis, we give a polynomial-time algorithm to solve List 3-Coloring for caterpillar-convex bipartite graphs, a super class of comb-convex bipartite graphs. Recognition algorithms are crucial in designing efficient algorithms. There are well-known algorithms for recognizing particular graph classes such as, bipartite graphs, and producing a corresponding representation for it. On the other hand, finding an efficient recognition algorithm gets harder as the graph class gets complex. Here we give a polynomial-time recognition algorithm for the class of caterpillar-convex bipartite graphs and give a caterpillar representation for it. This algorithm is further modified to give a polynomial-time recognition algorithm for a subclass of comb-convex bipartite graphs. As an application of list coloring problem we are interested in the Futoshiki Problem. Futoshiki is an NP-complete Latin Square Completion Type Puzzle. Considering Futoshiki puzzle as a constraint satisfaction problem, we first, give a list coloring based algorithm for it. Then we give two additional deterministic algorithms to compare its performance by computational experiments. Finally, we give algorithms that employ stochastic approaches including a Minimum Conflicts Algorithm, an Ant Colony Optimization Algorithm, and a Genetic Algorithm.
Benzer Tezler
- Performance and computational analysis of polarization-adjusted convolutional (PAC) codes
Kutupsal ve polarizayson ayarlı evrişimli (PAC) kodlarının performans ve hesaplama analizi
MOHSEN MORADI
Doktora
İngilizce
2022
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ERDAL ARIKAN
- Öbek analizi algoritmaları
Başlık çevirisi yok
MUHAMMET ALTUN
Yüksek Lisans
Türkçe
1998
Mühendislik Bilimleriİstanbul Teknik ÜniversitesiMühendislik Bilimleri Ana Bilim Dalı
YRD. DOÇ. DR. ALİ ERCENGİZ
- Üretim çizelgeleme algoritmalarının programlanması
Programming of production scheduling algorithms
SELMA AYŞE ÖZEL
Yüksek Lisans
Türkçe
1999
Endüstri ve Endüstri MühendisliğiUludağ ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ERDAL EMEL
- A feedback star identification algorithm via regularized pattern recognition using a unique feature extraction
Özgün öznitelikler ile regülarizasyon ve örüntü tanıma tabanlı geri bildirimli yıldız tanıma algoritması
ERDEM ONUR ÖZYURT
Doktora
İngilizce
2024
Havacılık ve Uzay Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. ALİM RÜSTEM ASLAN
- Design of a reduced complexity rateless spinal decoder
Düşük karmaşıklıklı, oransız filiz veren kod çözücü tasarımı
MURAT TAŞ
Yüksek Lisans
İngilizce
2014
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. MELEK DİKER