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

Unit disk graph coloring and its reoptimization

Basit öğe kaydını göster

dc.contributor Graduate Program in Industrial Engineering.
dc.contributor.advisor Ekim Aşıcı, Tınaz.
dc.contributor.author Boyacı, Arman.
dc.date.accessioned 2023-03-16T10:28:02Z
dc.date.available 2023-03-16T10:28:02Z
dc.date.issued 2009.
dc.identifier.other IE 2009 B67
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/13222
dc.description.abstract A unit disk graph (UDG) is a graph of intersection of a set of unit disks in Euclidean plane. Motivated by frequency assignment problem in telecommunication, we consider minimum vertex coloring of unit disk graphs (ColorUDG) and its reoptimization which are both NP-hard problems. In the first part of the study, the quality of lower and upper bounds on the optimal value of ColorUDG are investigated by conducting empirical tests. Maximum clique is a lower bound for the minimum coloring. Based on some observations, running time improvement is achieved on the existing O(n4.5) maximum clique algorithm. On the other hand, we derive upper bounds by some simple heuristics (sequential algorithms). Two new construction heuristics and a new improvement method are proposed. In the second part, vertex adding/removing reoptimization problems for ColorUDG are defined. Despite the knowledge of the optimum solution of the old instance, we showed that both problems remains NP-hard, therefore some heuristic methods are proposed. The developed reoptimization algorithms, which perform successfully for many instances when applied to randomly generated graphs. Moreover, we modified Brelaz’s sequential coloring algorithm to solve exactly vertex adding reoptimization problem.
dc.format.extent 30cm.
dc.publisher Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2009.
dc.relation Includes appendices.
dc.relation Includes appendices.
dc.subject.lcsh Euclidean algorithm.
dc.title Unit disk graph coloring and its reoptimization
dc.format.pages xii, 85 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