On the collapse of graphs related to scale-free networks
Bing Yao, Hongyu Wang, Yao Ming, Xiang'en Chen, Chao Yang, Xiaomin Zhang · 2013
Connected Dominating Set Problem is a fundamental problem in connected facility location and studied intensively in computer science and operations research and it is also a central problem in wireless networking. Maximum Leaf Spanning Tree Problem (MLSTP) is related with investigating scale-free networks. We investigate the collapse of graphs since “robust yet fragile” is an important character of scale-free networks, and provide two algorithms to approximate MLSTP.