Name
Title | ||
|---|---|---|
On Multi-Path Routing For Reliable Communications In Failure Interdependent Complex Networks |
Abstract | ||
|---|---|---|
This paper studies several new multiple routing path computation problems in failure-interdependent complex networks such as smart grid communication network, each of which exhibits unique failure interdependency. Despite the difference of the formulation of the problems, we show that each of the problems can be reduced to another within polynomial time, and therefore they are equivalent in terms of hardness. Then, we show that they are not only NP-hard, but also cannot be approximated within a certain bound unless P = NP. Besides, we show that their decision versions to determine if there exist two failure independent paths between two given end nodes are still NP-complete. Finally, a series of heuristic algorithms are proposed to deal with the daunting hardness of the problems. Most importantly, this paper opens a new series of research problems with daunting complexity based on important real world applications. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/s10878-020-00665-2 | JOURNAL OF COMBINATORIAL OPTIMIZATION |
Keywords | DocType | Volume |
Smart grid communication network, Multi-path routing, Maximum non-disrupting paths problem, NP-hard, Hardness of approximation | Journal | 41 |
Issue | ISSN | Citations |
1 | 1382-6905 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zishen Yang | 1 | 0 | 1.01 |
| Wei Wang | 2 | 0 | 0.68 |
| Kim Donghyun | 3 | 458 | 41.00 |