Robust recoverable path using backup nodes

M. van den Akker; H.L. Bodlaender; T.C. van Dijk; H. Hoogeveen; E. van Ommeren

doi:10.1007/978-3-662-49192-8_8

Robust recoverable path using backup nodes

M. van den Akker
, H.L. Bodlaender
, T.C. van Dijk
, H. Hoogeveen
, E. van Ommeren

Algorithms

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

Samenvatting

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.

Originele taal-2	Engels
Titel	SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings
Uitgeverij	Springer
Pagina's	95-106
Aantal pagina's	12
ISBN van geprinte versie	9783662491911
DOI's	https://doi.org/10.1007/978-3-662-49192-8_8
Status	Gepubliceerd - 2016
Evenement	42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016) - Harrachov, Tsjechië Duur: 23 jan. 2016 → 28 jan. 2016 Congresnummer: 42

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9587
ISSN van geprinte versie	03029743
ISSN van elektronische versie	16113349

Congres

Congres	42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016)
Verkorte titel	SOFSEM 2016
Land/Regio	Tsjechië
Stad	Harrachov
Periode	23/01/16 → 28/01/16

Toegang tot document

10.1007/978-3-662-49192-8_8

Andere bestanden en links

Link to publication in Scopus

Citeer dit

van den Akker, M., Bodlaender, H. L., van Dijk, T. C., Hoogeveen, H., & van Ommeren, E. (2016). Robust recoverable path using backup nodes. In SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings (blz. 95-106). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9587). Springer. https://doi.org/10.1007/978-3-662-49192-8_8

van den Akker, M. ; Bodlaender, H.L. ; van Dijk, T.C. et al. / Robust recoverable path using backup nodes. SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Springer, 2016. blz. 95-106 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7822628bb97546adbe9789cd9fdf4e85,

title = "Robust recoverable path using backup nodes",

abstract = "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 {\textquoteleft}backup nodes:{\textquoteright} 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.",

author = "\{van den Akker\}, M. and H.L. Bodlaender and \{van Dijk\}, T.C. and H. Hoogeveen and \{van Ommeren\}, E.",

year = "2016",

doi = "10.1007/978-3-662-49192-8\_8",

language = "English",

isbn = "9783662491911",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "95--106",

booktitle = "SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings",

address = "Germany",

note = "42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), SOFSEM 2016 ; Conference date: 23-01-2016 Through 28-01-2016",

}

van den Akker, M, Bodlaender, HL, van Dijk, TC, Hoogeveen, H & van Ommeren, E 2016, Robust recoverable path using backup nodes. in SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9587, Springer, blz. 95-106, 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), Harrachov, Tsjechië, 23/01/16. https://doi.org/10.1007/978-3-662-49192-8_8

Robust recoverable path using backup nodes. / van den Akker, M.; Bodlaender, H.L.; van Dijk, T.C. et al.
SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Springer, 2016. blz. 95-106 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9587).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Robust recoverable path using backup nodes

AU - van den Akker, M.

AU - Bodlaender, H.L.

AU - van Dijk, T.C.

AU - Hoogeveen, H.

AU - van Ommeren, E.

N1 - Conference code: 42

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 - https://www.scopus.com/pages/publications/84956693362

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

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 95

EP - 106

BT - SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings

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 -

van den Akker M, Bodlaender HL, van Dijk TC, Hoogeveen H, van Ommeren E. Robust recoverable path using backup nodes. In SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Springer. 2016. blz. 95-106. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-49192-8_8

Robust recoverable path using backup nodes

Samenvatting

Publicatie series

Congres

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit