Low‐connectivity network design on series‐parallel graphs
Siranjeevi Srinivasa Raghavan · Networks · 2004
Abstract Network survivability is a critical issue for modern fiber‐optic telecommunication networks. Networks with alternate routes between pairs of nodes permit users to communicate in the face of equipment failure. In this paper, we consider the following low‐connectivity network design (LCND) problem: Given a graph G = (N, E) and a connectivity requirement di ∈ {0, 1, 2} for each node and edge costs ce for each edge e ∈ E, design a minimum‐cost network that contains at least dst = min{ds, dt} disjoint paths between nodes s and t. We present linear‐time algorithms for both node‐ and edge‐connectivity versions of the problem on series‐parallel graphs. Due to the sparsity of telecommunications networks, this algorithm can be applied to obtain partial solutions and decompositions that may be embedded in a heuristic solution procedure as well as exact solution algorithms for the problem on general graphs. © 2004 Wiley Periodicals, Inc.