Ph.D. Theses
Permanent URI for this collection
Browse
Browsing Ph.D. Theses by Author "Aşıcı, Tınaz Ekim."
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item A decomposition approach to solve the selective graph coloring problem(Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2018., 2018.) Şeker, Oylum.; Aşıcı, Tınaz Ekim.; Taşkın, Zeki Caner.Graph coloring is the problem of assigning a minimum number of colors to all vertices of a graph such that no two vertices that are linked by an edge receive the same color. The selective graph coloring problem is a generalization of the standard graph coloring problem; given a graph with a partition of its vertex set into clusters, the aim is to pick exactly one vertex per cluster so that, among all possible selections, the number of colors needed to color the vertices in the selection is minimum. In this study, we focus on a decomposition based exact solution framework for selective coloring, and apply it rst to some special graph families, and then to general graphs with no particular structure. The special classes of graphs that we consider are perfect graphs and some special subclasses of perfect graphs, which are permutation, generalized split, and chordal graphs. In order to test the performance of our solution approach, we need graph instances from these graph classes, which led us to concentrate on the generation of random graphs from the graph classes under consideration in the second part of this study. We then test the decomposition method on graphs with di erent sizes and densities that we have produced with our generation methods, present computational results and compare them with an integer programming formulation of the problem solved by CPLEX, and a state-of-the-art algorithm from the literature. Our computational experiments indicate that our decomposition approach signi cantly improves the solution performance, especially in low-density graphs in permutation and generalized split graphs, and regardless of the edge-density in the class of chordal graphs. For perfect graphs in their general form, our approach outperforms both of the other two methods. In the case of general graphs, however, further improvements are needed to make our method competitive with the alternative methods we compare with.Item Graphs of edge-intersecting non-splitting paths(Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2015., 2015.) Boyacı, Arman.; Aşıcı, Tınaz Ekim.In this work, we introduce and study a new graph class: namely the graphs of Edge-Intersecting Non-Splitting Paths (ENP). First, we consider a special case where the host graph is a tree: the graphs of Edge-Intersecting Non-Splitting Paths in a Tree (ENPT). We study the characterization of the ENPT representations of chordless cycles (holes) which are one of the important basic graph structures. Under some assumption, we give an algorithm that returns the unique minimal representation if it exists. However, we show that the problem is NP-complete in general that is when this assumption does not necessarily hold. Then, we consider a more general case for which the host graph can be an arbitrary graph. As opposed to the Edge Intersection Graphs of Paths in an arbitrary graph which includes all graphs, we show that this is not true for ENP that is there exist some graphs which are not ENP. We also show that the class ENP coincides with the family of graphs of Edge-Intersecting and Non-Splitting Paths in a Grid (ENPG). Following similar studies for EPG graph class, we study the implications of restricting the number of bends of the individual paths in the grid. We show that restricting the number of bends also restricts the graph class. More concretely, by restricting the number of bends one gets an infinite sequence of classes such that every class is properly included in the next one. In particular, we show that one bend ENPG graphs are properly included in two bend ENPG graphs. In addition, we show that trees and cycles are one bend ENPG graphs, and characterize split graphs and co-bipartite graphs that are one bend ENPG. We prove that the recognition problem of one bend ENPG graphs is NP-complete even in a very restricted subclass of split graphs. Last, we provide a linear time recognition algorithm for one bend ENPG co-bipartite graphs.