Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

On the complexity of resilient network design

Publiceringsår: 2010
Språk: Engelska
Sidor: 108-118
Publikation/Tidskrift/Serie: Networks
Volym: 55
Nummer: 2
Dokumenttyp: Artikel i tidskrift
Förlag: John Wiley & Sons


In this article we prove NP-hardness of two well-known

optimization problems related to the design of multicommodity

flow networks with two different methods

for providing network resiliency against failures: path

diversity and flow restoration. Path diversity is a static

mechanism that consists of using, for each demand, a

number of paths and oversizing the flows assigned to

these paths so that for any failure the total surviving flow

is not less than the volume of the demand. By contrast,

flow restoration is a dynamic mechanism that consists

of reassigning the failed flows to backup paths when a

failure occurs. Both mechanisms are of practical interest

because although flow restoration is in general superior

to path diversity in terms of the required amount of

resource capacity, it might be too complicated to implement.

By providing an appropriate reduction from the

fractional graph coloring problem, we show that both

problems are NP-hard in the general case of failure

scenarios that admit simultaneous failures of multiple

links. Finally, we discuss how to efficiently solve the two

problems using path generation techniques.


  • Electrical Engineering, Electronic Engineering, Information Engineering


  • Networking-lup-obsolete
  • ISSN: 1097-0037

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