Unit disk graph coloring and its reoptimization

Abstract

Bir takım birim diskin Öklid düzleminde kesişimleri birim disk çizgedir(BDÇ).Özellikle telekomünikasyondaki frekans atama probleminin ¸cözümü için önemli ve NPzorproblemler olan birim disk çizge boyama(BDÇBoya) problemini ve yeniden eniyilenmesiniele aldık. Çalışmanın ilk kısmında, deneysel testler gerçekleşstirerek BDÇBoyaprobleminin alt ve üst sınırlarının kalitesi incelendi. Bazı gözlemlere dayanarak, mevcutO(n4.5) klik algoritmasının ortalama koşu zamanında iyileştirme sağlandı. Ekolarak, iki yeni boyama sezgiseli ve Kempe'nin Zincirlerinden ilham alınarak yenibir iyileştirme yöntemi önerildi. İkinci kısımda ise, köşe ekle/çıkar yeniden eniyilemeproblemleri tanımlandı. Eski örneğe ait eniyi çözüm bilgisine rağmen bu problemlerinNP-zor kaldıklarını gösterdik ve bu nedenle sezgisel yöntemler önerdik. Bu sezgisellerinortalama performansları, deneysel çalışmalar ile tayin edildi. Ayrıca Brelaz'ınardışık boyama algoritmasını köşe ekle yeniden eniyileme problemini ¸çözebilecek şekildeuyarladık.

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(n^{4.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.