Static and dynamic routing under disjoint dominant extreme demands

This paper considers a special case of the robust network design problem where the dominant extreme points of the demand polyhedron have a disjoint support. In this case static and dynamic routing lead to the same optimal solution, both for the splittable and the unsplittable case. As a consequence, the robust network design problem with (splittable) dynamic routing is polynomially solvable, whereas it is co-NP-hard in the general case. This result applies to particular instances of the single-source Hose model. © 2010 Elsevier B.V. All rights reserved.SCOPUS: ar.j