ISSN:
1572-9125
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract The generalized Steiner problem (GSP) is concerned with the determination of a minimum cost subnetwork of a given network where some (not necessarily all) vertices satisfy certain pairwise (vertex or edge) connectivity requirements. The GSP has applications to the design of water and electricity supply networks, communication networks and other large-scale systems where connectivity requirements ensure the communication between the selected vertices when some vertices and/or edges can become inoperational due to scheduled maintenance, error, or overload. The GSP is known to beNP-complete. In this paper we show that if the subnetwork is required to be biconnected or respectively edge-biconnected, and the underlying network is outerplanar, the GSP can be solved in linear time.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01935369
