Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Complexity of resilient network optimisation

Författare

  • Mateusz Zotkiewicz
  • Michal Pioro
  • Artur Tomaszewski

Summary, in English

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.

Publiceringsår

2009

Språk

Engelska

Sidor

701-709

Publikation/Tidskrift/Serie

European Transactions on Telecommunications

Volym

20

Issue

7

Dokumenttyp

Artikel i tidskrift

Förlag

John Wiley & Sons Inc.

Ämne

  • Electrical Engineering, Electronic Engineering, Information Engineering

Status

Published

Forskningsgrupp

  • Networking

ISBN/ISSN/Övrigt

  • ISSN: 1541-8251