Arşiv ve Dokümantasyon Merkezi
Dijital Arşivi

A decomposition approach to solve the selective graph coloring problem

Basit öğe kaydını göster

dc.contributor Ph.D. Program in Industrial Engineering.
dc.contributor.advisor Aşıcı, Tınaz Ekim.
dc.contributor.advisor Taşkın, Zeki Caner.
dc.contributor.author Şeker, Oylum.
dc.date.accessioned 2023-03-16T10:35:25Z
dc.date.available 2023-03-16T10:35:25Z
dc.date.issued 2018.
dc.identifier.other IE 2018 S44 PhD
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/13575
dc.description.abstract 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.
dc.format.extent 30 cm.
dc.publisher Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2018.
dc.subject.lcsh Graph coloring.
dc.title A decomposition approach to solve the selective graph coloring problem
dc.format.pages xvii, 137 leaves ;


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım