Dominating tree problem heuristics for scale-free networks

The Dominating Tree Problem (DTP) aims to find a dominating tree T ^∗⊂ G ₀ of minimum total edge weight on a given undirected connected graph G ₀. The most common heuristic approach for this problem considers Kruskal’s Algorithm, an ideal choice for minimizing the total edge weights of the generated T ^∗. In this paper, we focus on a DTP heuristics applied to a special class of graphs called scale-free networks. The proposed algorithm exploits the scale-free property of vertex degree distribution p(k) of G ₀ such that a considerable improvement in computational time is achieved.