Two-Connected Augmentation Problems in Planar Graphs |
| |
Authors: | J Scott Provan Roger C Burk |
| |
Institution: | a Department of Operations Research, University of North Carolina, Chapel Hill, North Carolina, 27599-3180;b The Aerospace Corporation, Chantilly, Virginia, 20151 |
| |
Abstract: | Given a weighted undirected graph G and a subgraph S of G, we consider the problem of adding a minimum-weight set of edges of G to S so that the resulting subgraph satisfies specified (edge or vertex) connectivity requirements between pairs of nodes of S. This has important applications in upgrading telecommunication networks to be invulnerable to link or node failures. We give a polynomial algorithm for this problem when S is connected, nodes are required to be at most 2-connected, and G is planar. Applications to network design and multicommodity cut problems are also discussed. |
| |
Keywords: | planar graphs augmentation biconnectivity vulnerability multicommodity cuts network design |
本文献已被 ScienceDirect 等数据库收录! |
|