On multi-path routing for reliable communications in failure interdependent complex networks

Zishen Yang, Wei Wang () and Donghyun Kim
Additional contact information
Zishen Yang: Xi’an Jiaotong University
Wei Wang: Xi’an Jiaotong University
Donghyun Kim: Georgia State University

Journal of Combinatorial Optimization, 2021, vol. 41, issue 1, No 12, 170-196

Abstract: 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 $$\mathcal {NP}$$ NP -hard, but also cannot be approximated within a certain bound unless $${\mathcal {P}}=\mathcal {NP}$$ 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 $$\mathcal {NP}$$ 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.

Keywords: Smart grid communication network; Multi-path routing; Maximum non-disrupting paths problem; $$\mathcal {NP}$$ NP -hard; Hardness of approximation (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00665-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:1:d:10.1007_s10878-020-00665-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00665-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().