Minimum Color-spanning Tree

Please enable javascript in your browser.

Zafar Asadollahpoor, Pooya | 2013

1363 Viewed

Type of Document: M.Sc. Thesis
Language: Farsi
Document No: 44737 (19)
University: Sharif University of Technology
Department: Computer Engineering
Advisor(s): Abam, Mohammad Ali
Abstract:
In the general case of minimum color-spanning tree which is one of the color-spanning set problems, given a weighted graph with n vertices of k different colors, the goal is to find a subtree of minimum weight such that vertices of this subtree include all the colors in the graph. In the planar case, the input is a complete graph with n colored vertices on the plane and the weight of each edge is the Euclidean distance between its corresponding vertices. In this thesis we consider the problem of minimum color-spanning tree. To this end, first we present various color-spanning set problems and some other related problems like Steiner tree and we study the previous work on these problems. Then we prove both the general and planar cases of the problem belong to NP-hard class and we consider the relation of these problems to several other problems with respect to level of hardness. Next we propose an approximation algorithm of 3√k factor for the planar case. Finally we present a special case of the problem with the proof of its hardness
Keywords:
Approximate Algorithm ; Minimum Color-Spanning Tree ; Color-Spanning Set ; Steiner Tree ; NP-Hard Problems