Low Connectivity Network Design on Series-Parallel Graphs
| dc.contributor.author | Raghavan, S. | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T10:10:48Z | |
| dc.date.available | 2007-05-23T10:10:48Z | |
| dc.date.issued | 2001 | en_US |
| dc.description.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 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.extent | 365275 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/6205 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 2001-38 | en_US |
| dc.subject | Global Communication Systems | en_US |
| dc.title | Low Connectivity Network Design on Series-Parallel Graphs | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1