Du är här

Complexity of resilient network optimisation

Författare:
Publiceringsår: 2009
Språk: Engelska
Sidor: 701-709
Publikation/Tidskrift/Serie: European Transactions On Telecommunications
Volym: 20
Nummer: 7
Dokumenttyp: Artikel
Förlag: John Wiley & Sons Ltd

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering

Övrigt

Published
Yes
  • Networking
  • ISSN: 1124-318X

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen

LERU logo U21 logo