Back to Search
Start Over
Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming.
- Source :
-
Mathematical Programming . May2018, Vol. 169 Issue 1, p255-275. 21p. - Publication Year :
- 2018
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 169
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 129037478
- Full Text :
- https://doi.org/10.1007/s10107-018-1242-z