Generalized Steiner problem in outerplanar networks

DOI10.1007/BF01935369MaRDI QIDQ1074505zbMATH OpenOpenAlexFDO

Authors Pawel Winter

Publication date 1985

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01935369

zbMATH Keywords

connectivity constraintsgeneralized Steiner problemlinear time algorithmouterplanar network

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Review text

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.

Recommendations

• Generalized steiner problem in series-parallel networks
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Polynomially solvable special cases of the Steiner problem in planar networks
• Some generalizations of the steiner problem in graphs
• A 3/2-approximation algorithm for generalized Steiner trees in complete graphs with edge lengths 1 and 2

Cites work

• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 3742993 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3614802 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Steiner trees, partial 2–trees, and minimum IFI networks
• Steiner's problem in graphs and its implications

Cited in

(15)

• Problems with generalized Steiner problems
• Tree polytope on 2-trees
• On survivable network polyhedra
• On Steiner versions of (bi)connectivity in network problems
• A 2-approximation algorithm and beyond for the minimum diameter k-Steiner forest problem
• An optimal algorithm for an outerplanar facility location problem with improved time complexity
• On the Steiner 2-edge connected subgraph polytope
• scientific article; zbMATH DE number 4008433 (Why is no real title available?)
• Generalized steiner problem in series-parallel networks
• The line connectivity problem
• On the solution of the generalized steiner problem by the subgradient method
• In-trees and plane embeddings of outerplanar graphs
• On the dominant of the Steiner 2-edge connected subgraph polytope
• Extended formulation and branch-and-cut-and-price algorithm for the two connected subgraph problem with disjunctive constraints
• The Steiner forest problem revisited

This page was built for publication: Generalized Steiner problem in outerplanar networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1074505)