Yaşar Diner, Öznur

Profile Picture
Name Variants
Yaşar Diner, Öznur
Yaşar Diner,Ö.
Oznur, Yasar Diner
O. Yaşar Diner
Yasar Diner, Oznur
Y., Öznur
Oznur Yaşar Diner
Yasar Diner,Ö.
Yaşar Diner, Ö.
YAŞAR DINER, ÖZNUR
YAŞAR DINER, Öznur
Y.,Oznur
Yasar Diner,O.
Öznur Yaşar Diner
Yaşar Diner, ÖZNUR
Yaşar Diner, O.
Y., Oznur
Ö. Yaşar Diner
ÖZNUR YAŞAR DINER
Yaşar Diner, Oznur
Yasar Diner,Oznur
Öznur YAŞAR DINER
Diner, Öznur Yaşar
Diner, Oznur Yasar
Diner, Ö.Y.
Job Title
Dr. Öğr. Üyesi
Email Address
oznur.yasar@khas.edu.tr
Main Affiliation
Computer Engineering
Status
Website
ORCID ID
0000-0002-9271-2691
Scopus Author ID
58777832500
Turkish CoHE Profile ID
Google Scholar ID
WoS Researcher ID
AAT-7443-2020
Scholarly Output

17

Articles

9

Citation Count

0

Supervised Theses

1

Filters

2021 - 20247
Reset filters

Settings

Has files: false

Scholarly Output Search Results

Now showing 1 - 7 of 7
  • Thumbnail Image
    Article
    Citation - WoS: 0
    Citation - Scopus: 0
    List Coloring Based Algorithm for the Futoshiki Puzzle
    (Ramazan Yaman, 2024) Yaşar Diner, Öznur; Ş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.
  • Thumbnail Image
    Book Part
    Citation - Scopus: 7
    On List K-Coloring Convex Bipartite Graphs
    (Springer Nature, 2021) Diaz, Josep; Yaşar Diner, Öznur; Diner, Öznur Yaşar; Serna, Maria; Oriol, Serra
    List k-Coloring (Lik-Col) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1, 2, …, k}. The problem is known to be NP-hard even for k = 3 within the class of 3-regular planar bipartite graphs and for k = 4 within the class of chordal bipartite graphs. In 2015 Huang, Johnson and Paulusma asked for the complexity of Li 3-Col in the class of chordal bipartite graphs. In this paper, we give a partial answer to this question by showing that Lik-Col is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright et al. (SIAM J Discrete Math 28(4):1675–1685, 2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the Lik-Col in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LiH-Col problem on convex bipartite graphs.
  • Thumbnail Image
    Article
    Citation - WoS: 0
    Citation - Scopus: 0
    On minimum vertex bisection of random d-regular graphs
    (Academic Press inc Elsevier Science, 2024) Yaşar Diner, Öznur; Diner, Oznur Yasar; Serna, Maria; Serra, Oriol
    Minimum vertex bisection is a graph partitioning problem in which the aim is to find a partition of the vertices into two equal parts that minimizes the number of vertices in one partition set that have a neighbor in the other set. In this work we are interested in providing asymptotically almost surely upper bounds on the minimum vertex bisection of random d -regular graphs, for constant values of d . Our approach is based on analyzing a greedy algorithm by using the differential equation method. In this way, we obtain the first known non -trivial upper bounds for the vertex bisection number in random regular graphs. The numerical approximations of these theoretical bounds are compared with the emprical ones, and with the lower bounds from Kolesnik and Wormald (2014) [30]. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).
  • Thumbnail Image
    Article
    Citation - WoS: 0
    The Multicolored Graph Realization Problem
    (Elsevier, 2024) Diaz, Josep; Yaşar Diner, Öznur; Diner, Oznur Yasar; Serna, Maria; Serra, Oriol
    We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph ( G , phi ), i.e., a graph G together with a coloring phi on its vertices. We associate each colored graph ( G , phi ) with a cluster graph ( G phi ) in which, after collapsing all vertices with the same color to a node, we remove multiple edges and self -loops. A set of vertices S is multicolored when S has exactly one vertex from each color class. The MGR problem is to decide whether there is a multicolored set S so that, after identifying each vertex in S with its color class, G [ S ] coincides with G phi . The MGR problem is related to the well-known class of generalized network problems, most of which are NP -hard, like the generalized Minimum Spanning Tree problem. The MGR is a generalization of the multicolored clique problem, which is known to be W [ 1 ] -hard when parameterized by the number of colors. Thus, MGR remains W [ 1 ] - hard, when parameterized by the size of the cluster graph. These results imply that the MGR problem is W [ 1 ] -hard when parameterized by any graph parameter on G phi , among which lies treewidth. Consequently, we look at the instances of the problem in which both the number of color classes and the treewidth of G phi are unbounded. We consider three natural such graph classes: chordal graphs, convex bipartite graphs and 2 -dimensional grid graphs. We show that MGR is NP -complete when G phi is either chordal, biconvex bipartite, complete bipartite or a 2 -dimensional grid. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds even for graphs with bounded degree. We provide a complexity dichotomy with respect to cluster size. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
  • Thumbnail Image
    Conference Object
    Citation - WoS: 0
    Block Elimination Distance
    (Springer international Publishing Ag, 2021) Yaşar Diner, Öznur; Giannopoulou, Archontia C.; Stamoulis, Giannos; Thilikos, Dimitrios M.
    We introduce the parameter of block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class G, the class B(G) contains all graphs whose blocks belong to G and the class A(G) contains all graphs where the removal of a vertex creates a graph in G. Given a hereditary graph class G, we recursively define G((k)) so that G((0)) = B(G) and, if k >= 1, G((k)) = B(A(G((k-1)))). The block elimination distance of a graph G to a graph class G is the minimum k such that G is an element of G((k)) and can be seen as an analog of the elimination distance parameter, defined in [J. Bulian & A. Dawar. Algorithmica, 75(2):363-382, 2016], with the difference that connectivity is now replaced by biconnectivity. We show that, for every non-trivial hereditary class G, the problem of deciding whether G. G(k) is NPcomplete. We focus on the case where G is minor-closed and we study the minor obstruction set of G((k)) i.e., the minor-minimal graphs not in G((k)). We prove that the size of the obstructions of G((k)) is upper bounded by some explicit function of k and the maximum size of a minor obstruction of G. This implies that the problem of deciding whether G is an element of G((k)) is constructively fixed parameter tractable, when parameterized by k. Our results are based on a structural characterization of the obstructions of B(G), relatively to the obstructions of G. Finally, we give two graph operations that generate members of G((k)) from members of G((k-1)) and we prove that this set of operations is complete for the class O of outerplanar graphs. This yields the identification of all members O boolean AND G((k)), for every k is an element of N and every non-trivial minor-closed graph class G.
  • Thumbnail Image
    Conference Object
    Citation - Scopus: 0
    List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs
    (Springer Science and Business Media Deutschland GmbH, 2024) Baklan Şen,B.; Yaşar Diner, Öznur; Yaşar Diner,Ö.; Erlebach,T.
    Given a graph G= (V, E) and a list of available colors L(v) for each vertex v∈ V, where L(v) ⊆ { 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 3-Coloring is NP-complete even for bipartite graphs, and its complexity on comb-convex bipartite graphs has been an open problem. We give a polynomial-time algorithm to solve List 3-Coloring for caterpillar-convex bipartite graphs, a superclass of comb-convex bipartite graphs. We also give a polynomial-time recognition algorithm for the class of caterpillar-convex bipartite graphs. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
  • Thumbnail Image
    Doctoral Thesis
    Computational Complexity of List Coloring and Its Variants for Particular Graph Classes
    (2023) Şen, Banu Baklan; Yaşar Diner, Öznur; 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.