Show simple item record

Low Connectivity Network Design on Series-Parallel Graphs

dc.contributor.authorRaghavan, S.en_US
dc.date.accessioned2007-05-23T10:10:48Z
dc.date.available2007-05-23T10:10:48Z
dc.date.issued2001en_US
dc.identifier.urihttp://hdl.handle.net/1903/6205
dc.description.abstractNetwork 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 o(i) in (0,1,2) for each node, design a network at minimum cost that contains at least o(st) = min(o(s),o(t)) 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.en_US
dc.format.extent365275 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 2001-38en_US
dc.subjectGlobal Communication Systemsen_US
dc.titleLow Connectivity Network Design on Series-Parallel Graphsen_US
dc.typeTechnical Reporten_US
dc.contributor.departmentISRen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record