Öznur Yaşar Diner

Yaşar Diner, Öznur

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

ORCID ID

0000-0002-9271-2691

Scopus Author ID

58777832500

Full item page

Scholarly Output

17

Articles

9

Citation Count

0

Supervised Theses

1 Scholarly Output Search Results

Now showing 1 - 10 of 17

Citation Count: 5
Three-fast-searchable graphs
(Elsevier Science Bv, 2013) Dereniowski, Dariusz; Diner, Öznur Yaşar; Dyer, Danny
In the edge searching problem searchers move from vertex to vertex in a graph to capture an invisible fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which at every move a new edge of the graph G must be guaranteed to be free of the intruder. That is once all searchers are placed the graph G is cleared in exactly vertical bar E(G)vertical bar moves. Such a restriction obviously necessitates a larger number of searchers. We examine this model and characterize graphs for which 2 or 3 searchers are sufficient. We prove that the corresponding decision problem is NP-complete. (C) 2013 Elsevier B.V. All rights reserved.
Citation Count: 1
Block Elimination Distance
(Springer Japan Kk, 2022) Diner, Oznur Yasar; 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))) ) N We show that, for every nontrivial hereditary class g, the problem of deciding whether G is an element of G((k)) is NP-complete. 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 ofk 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. 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.Please check and confirm if the authors Given and Family names have been correctly identified for author znur YaYar Diner. All authors names have been identified conectly. Please confirm if the corresponding author is correctly identified. Amend if necessary.This is correct
Citation Count: 0
On minimum vertex bisection of random d-regular graphs
(Academic Press inc Elsevier Science, 2024) Diaz, Josep; 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/).
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.
Citation Count: 0
Block Elimination Distance
(Springer international Publishing Ag, 2021) Diner, Oznur Yasar; 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.
Citation Count: 9
Contraction Blockers for Graphs With Forbidden Induced Paths
(Springer-Verlag Berlin, 2015) Diner, Öznur Yaşar; Paulusma, Daniel; Picouleau, Christophe; Ries, Bernard
We consider the following problem: can a certain graph parameter of some given graph be reduced by at least d for some integer d via at most k edge contractions for some given integer k? We examine three graph parameters: the chromatic number clique number and independence number. For each of these graph parameters we show that when d is part of the input this problem is polynomial-time solvable on P-4-free graphs and NP-complete as well as W[1]-hard with parameter d for split graphs. As split graphs form a subclass of P-5-free graphs both results together give a complete complexity classification for P-l-free graphs. The W[1]-hardness result implies that it is unlikely that the problem is fixed-parameter tractable for split graphs with parameter d. But we do show on the positive side that the problem is polynomial-time solvable for each parameter on split graphs if d is fixed i.e. not part of the input. We also initiate a study into other subclasses of perfect graphs namely cobipartite graphs and interval graphs.
Citation Count: 10
Contraction and Deletion Blockers for Perfect Graphs and H-Free Graphs
(Elsevier Science, 2018) Diner, Öznur Yaşar; Paulusma, Daniel; Picouleau, Christophe; Ries, Bernard
We study the following problem: for given integers d k and graph G can we reduce some fixed graph parameter pi of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number chi clique number omega and independence number alpha and as operations we choose edge contraction ec and vertex deletion vd. We determine the complexity of this problem for S = {ec} and S = {vd} and pi is an element of{chi omega alpha} for a number of subclasses of perfect graphs. We use these results to determine the complexity of the problem for S = {ec} and S = {vd} and pi is an element of{chi omega alpha} restricted to H-free graphs. (C) 2018 Elsevier B.V. All rights reserved.
Citation Count: 0
The Multicolored Graph Realization Problem
(Elsevier B.V., 2022) Díaz, J.; Diner, Ö.Y.; Serna, M.; Serra, O.
We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph (G,?), i.e., a graph G together with a coloring ? on its vertices. We associate each colored graph (G,?) with a cluster graph (G?) 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?. 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?, 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? 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? 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. © 2022 The Author(s)
Citation Count: 11
Strategic Early Warning System for the French Milk Market: a Graph Theoretical Approach To Foresee Volatility
(Elsevier, 2017) Bisson, Christophe; Diner, Öznur Yaşar
This paper presents a new approach for developing a Strategic Early Warning System aiming to better detect and interpret weak signals. We chose the milk market as a case study in line with the recent call from the EU Commission for governance tools which help to better address such highly volatile markets. Furthermore on the first of April 2015 the new Common Agricultural Policy ended quotas for milk which led to a milk crisis in the EU. Thus we collaborated with milk experts to get their inputs for a new model to analyse the competitive environment. Consequently we constructed graphs to represent the major factors that affect the milk industry and the relationships between them. We obtained several network measures for this social network such as centrality and density. Some factors appear to have the largest major influence on all the other graph elements while others strongly interact in cliques. Any detected changes in any of these factors will automatically impact the others. Therefore scanning ones competitive environment can allow an organisation to get an early warning to help it avoid an issue (as much as possible) and/or seize an opportunity before its competitors. We conclude that Strategic Early Warning Systems as a corporate foresight approach utilising graph theory can strengthen the governance of markets. (C) 2017 Elsevier Ltd. All rights reserved.
Citation Count: 0
Searching Circulant Graphs
(2011) Diner, Öznur Yaşar; Dyer, Danny
[Abstract Not Available]