Browsing by Author "Diner, Öznur Yaşar"
Now showing 1 - 8 of 8
- Results Per Page
- Sort Options
Conference Object Citation Count: 0Bayesian and Graph Theory Approaches to Develop Strategic Early Warning Systems for the Milk Market(Springer-Verlag Berlin, 2015) Gürpınar, Furkan; Bisson, Christophe; Diner, Öznur YaşarThis paper presents frameworks for developing a Strategic Early Warning System allowing the estimatation of the future state of the milk market. Thus this research is in line with the recent call from the EU commission for tools which help to better address such a highly volatile market. We applied different multivariate time series regression and Bayesian networks on a pre-determined map of relations between macro economic indicators. The evaluation of our findings with root mean square error (RMSE) performance score enhances the robustness of the prediction model constructed. Finally we construct a graph to represent the major factors that effect the milk industry and their relationships. We use graph theoretical analysis to give several network measures for this social networkDoctoral Thesis Computational complexity of list coloring and ıts variants for particular graph classes(2023) Şen, Banu Baklan; Diner, Öznur YaşarHer 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.Article Citation Count: 10Contraction and deletion blockers for perfect graphs and H-free graphs(Elsevier Science, 2018) Diner, Öznur Yaşar; Paulusma, Daniel; Picouleau, Christophe; Ries, BernardWe 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.Conference Object Citation Count: 9Contraction Blockers for Graphs with Forbidden Induced Paths(Springer-Verlag Berlin, 2015) Diner, Öznur Yaşar; Paulusma, Daniel; Picouleau, Christophe; Ries, BernardWe 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.Book Part Citation Count: 6On list k-coloring convex bipartite graphs(Springer Nature, 2021) Diaz, Josep; Diner, Öznur Yaşar; Serna, Maria; Oriol, SerraList 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.Conference Object Citation Count: 0Article Citation Count: 11Strategic Early Warning System for the French milk market: A graph theoretical approach to foresee volatility(Elsevier, 2017) Bisson, Christophe; Diner, Öznur YaşarThis 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.Article Citation Count: 5Three-fast-searchable graphs(Elsevier Science Bv, 2013) Dereniowski, Dariusz; Diner, Öznur Yaşar; Dyer, DannyIn 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.
