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: an International Journal
Volym: 55
Nummer: 2
Dokumenttyp: Artikel


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
  • ISSN: 0028-3045

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