Name
Title | ||
|---|---|---|
Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming. |
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s10107-018-1242-z | Math. Program. |
Keywords | Field | DocType |
Fault-tolerant,Connectivity,DC programming,Convex function,90C27,90C26 | Numerical tests,Mathematical optimization,Spanning subgraph,Heuristic (computer science),Fault tolerance,Convex function,Dc programming,Mathematics | Journal |
Volume | Issue | ISSN |
169 | 1 | 0025-5610 |
Citations | PageRank | References |
1 | 0.36 | 16 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chenchen Wu | 1 | 26 | 13.84 |
| Yishui Wang | 2 | 4 | 5.51 |
| Zaixin Lu | 3 | 204 | 16.24 |
| Panos M. Pardalos | 4 | 141 | 19.60 |
| Dachuan Xu | 5 | 57 | 17.03 |
| Zhao Zhang | 6 | 706 | 102.46 |
| Ding-Zhu Du | 7 | 3497 | 283.06 |