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

linear time algorithmconnectivity constraintsgeneralized Steiner problemouterplanar network

Mathematics Subject Classification ID

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

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

• 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?)
• Depth-First Search and Linear Graph Algorithms
• 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

(14)

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

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)