Integer programming approaches to the Dominating Tree Problem

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2016

Öğrenci: SELİN AKİFOĞLU

Danışman: MUSTAFA KEMAL TURAL

Özet:

Let G=(V,E) be a simple undirected edge-weighted graph, where V and E denote the set of vertices and edges of G, respectively. The Dominating Tree Problem (DTP) searches for a minimum weighted tree in G, say DT, such that each vertex either belongs to DT or is one-hop away from DT. This problem is an NP-hard but a practical problem. The solution of the DTP is used to construct a backbone for wireless sensor networks, which have a wide usage in many industrial and consumer applications. In this thesis, different integer programming formulations of the problem are introduced. For some instances in the literature, optimal solutions are provided for the first time and for some others best known heuristic solutions are shown to be optimal. Moreover, branch-and-cut approach is applied to the problem.