Generalized Steiner problem in outerplanar networks (Q1074505): Difference between revisions

The generalized Steiner problem in a network is considered. The generalization consists in the requirement that some vertices satisfy certain pairwise (vertex or edge) connectivity constraints. The general problem was known to be NP-complete, but for the case when the underlying network is outerplanar and the subnetwork is required to be biconnected (or edge biconnected), a linear time algorithm is presented.