Advanced

Complexity of resilient network optimisation

Zotkiewicz, Mateusz; Pioro, Michal LU and Tomaszewski, Artur (2009) In European Transactions on Telecommunications 20(7). p.701-709
Abstract
Path restoration (PR) is one of the basic mechanisms for securing telecommunication networks against failures. In the paper, we discuss the complexity of certain variants of a multi-commodity flow network optimisation problem in directed graphs related to state-independent path restoration mechanisms. We demonstrate that most variants of the considered problem are NP-hard. Depending on the variant, we show how the problem can be reduced either from the partition problem or from the problem of finding an arc-disjoint pair of paths that connect two distinct pairs of nodes. We also demonstrate that at the same time the considered problem is difficult to approximate. The complexity results of the paper are important as they can help to devise... (More)
Path restoration (PR) is one of the basic mechanisms for securing telecommunication networks against failures. In the paper, we discuss the complexity of certain variants of a multi-commodity flow network optimisation problem in directed graphs related to state-independent path restoration mechanisms. We demonstrate that most variants of the considered problem are NP-hard. Depending on the variant, we show how the problem can be reduced either from the partition problem or from the problem of finding an arc-disjoint pair of paths that connect two distinct pairs of nodes. We also demonstrate that at the same time the considered problem is difficult to approximate. The complexity results of the paper are important as they can help to devise proper algorithms for resilient network design tools. Copyright (C) 2009 John Wiley & Soils, Ltd. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
European Transactions on Telecommunications
volume
20
issue
7
pages
701 - 709
publisher
John Wiley & Sons
external identifiers
  • wos:000271888600008
  • scopus:70449337765
ISSN
1541-8251
DOI
10.1002/ett.1371
language
English
LU publication?
yes
id
f4dc979c-c7c4-4ebf-92bc-3a3012a7b2a2 (old id 1518445)
date added to LUP
2010-01-13 10:16:20
date last changed
2017-01-01 05:06:10
@article{f4dc979c-c7c4-4ebf-92bc-3a3012a7b2a2,
  abstract     = {Path restoration (PR) is one of the basic mechanisms for securing telecommunication networks against failures. In the paper, we discuss the complexity of certain variants of a multi-commodity flow network optimisation problem in directed graphs related to state-independent path restoration mechanisms. We demonstrate that most variants of the considered problem are NP-hard. Depending on the variant, we show how the problem can be reduced either from the partition problem or from the problem of finding an arc-disjoint pair of paths that connect two distinct pairs of nodes. We also demonstrate that at the same time the considered problem is difficult to approximate. The complexity results of the paper are important as they can help to devise proper algorithms for resilient network design tools. Copyright (C) 2009 John Wiley & Soils, Ltd.},
  author       = {Zotkiewicz, Mateusz and Pioro, Michal and Tomaszewski, Artur},
  issn         = {1541-8251},
  language     = {eng},
  number       = {7},
  pages        = {701--709},
  publisher    = {John Wiley & Sons},
  series       = {European Transactions on Telecommunications},
  title        = {Complexity of resilient network optimisation},
  url          = {http://dx.doi.org/10.1002/ett.1371},
  volume       = {20},
  year         = {2009},
}