TY - GEN
T1 - Robust recoverable path using backup nodes
AU - van den Akker, Marjan
AU - Bodlaender, Hans L.
AU - van Dijk, Thomas C.
AU - Hoogeveen, Johannes
AU - van Ommeren, Erik
PY - 2016
Y1 - 2016
N2 - We consider routing in networks in the presence of node failures. The focus is specifically on the single-node failure model, which captures the resilience of networks in a realistic fault setting. We introduce a model of recoverable routing, where we ask for an s-t-path that can be repaired easily and locally by assigning ‘backup nodes:’ when a node on the path fails, it is replaced by its backup node. We resolve the basic algorithmic and complexity questions for finding paths in this model, depending on the properties we require of the backup assignment. For some cases we provide polynomial-time algorithms, and for the others we prove NP-completeness and provide exponential-time algorithms. Lastly, we consider a problem variant where the path is given and ask for a backup assignment.
AB - We consider routing in networks in the presence of node failures. The focus is specifically on the single-node failure model, which captures the resilience of networks in a realistic fault setting. We introduce a model of recoverable routing, where we ask for an s-t-path that can be repaired easily and locally by assigning ‘backup nodes:’ when a node on the path fails, it is replaced by its backup node. We resolve the basic algorithmic and complexity questions for finding paths in this model, depending on the properties we require of the backup assignment. For some cases we provide polynomial-time algorithms, and for the others we prove NP-completeness and provide exponential-time algorithms. Lastly, we consider a problem variant where the path is given and ask for a backup assignment.
UR - http://www.scopus.com/inward/record.url?scp=84956693362&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49192-8_8
DO - 10.1007/978-3-662-49192-8_8
M3 - Conference contribution
AN - SCOPUS:84956693362
SN - 9783662491911
VL - 9587
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 95
EP - 106
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PB - Springer
T2 - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2016
Y2 - 23 January 2016 through 28 January 2016
ER -