Browsing by Author "Şen, Banu Baklan"

Now showing 1 - 2 of 2

Computational Complexity of List Coloring and Its Variants for Particular Graph Classes
(2023) Şen, Banu Baklan; Diner, Öznur Yaşar
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.
List Coloring Based Algorithm for the Futoshiki Puzzle
(Ramazan Yaman, 2024) Şen, Banu Baklan; Diner, Oznur Yaşar
Given a graph G=(V, E) and a list of available colors L(v) for each vertex v\\in V, where L(v) \\subseteq {1, 2, ..., k}, List k-Coloring refers to the problem of assigning colors to the vertices of $G$ 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 k-Coloring, is NP-complete even for 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 which is efficient for small boards of fixed size. To thoroughly investigate the efficiency of our algorithm in comparison with a proposed backtracking-based algorithm, we conducted a substantial number of computational experiments at different difficulty levels, considering varying numbers of inequality constraints and given values. Our results from the extensive range of experiments indicate that the list coloring-based algorithm is much more efficient.