Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming |
| |
| Authors: | Chenchen Wu Yishui Wang Zaixin Lu Panos M Pardalos Dachuan Xu Zhao Zhang Ding-Zhu Du |
| |
| Institution: | 1.College of Science,Tianjin University of Technology,Xiqing District, Tianjin,People’s Republic of China;2.Department of Information and Operations Research, College of Applied Sciences,Beijing University of Technology,Beijing,People’s Republic of China;3.School of Engineering and Computer Science,Washington State University,Vancouver,USA;4.Department of Industrial and Systems Engineering,University of Florida,Gainesville,USA;5.Beijing Institute for Scientific and Engineering Computing,Beijing University of Technology,Beijing,People’s Republic of China;6.College of Mathematics Physics and Information Engineering,Zhejiang Normal University,Jinhua,People’s Republic of China;7.Department of Computer Science,University of Texa at Dallas,Richardson,USA |
| |
| Abstract: | In this paper, we consider the maximum and minimum versions of degree-concentrated fault-tolerant spanning subgraph problem which has many applications in network communications. We prove that both this two problems are NP-hard. For the maximum version, we use DC programming relaxation to propose a heuristic algorithm. Numerical tests indicate that the proposed algorithm is efficient and effective. For the minimum version, we also formulate it as a DC program, and show that the DC algorithm does not perform well for this problem. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
