Dominating tree problem heuristics for scale-free networks
K.P. Urog, JOHNROB Y. BANTANG, Henry N. Adorna · 2019
The Dominating Tree Problem (DTP) aims to find a dominating tree T ∗ ⊂ G 0 of minimum total edge weight on a given undirected connected graph G 0 . 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 0 such that a considerable improvement in computational time is achieved.