Generalized Steiner problem in outerplanar networks

DOI10.1007/BF01935369zbMath0589.90081OpenAlexW2050142375MaRDI QIDQ1074505

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)

Related Items

A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem ⋮ Problems with generalized Steiner problems ⋮ On survivable network polyhedra ⋮ On the dominant of the Steiner 2-edge connected subgraph polytope ⋮ On the Steiner 2-edge connected subgraph polytope ⋮ In-trees and plane embeddings of outerplanar graphs ⋮ Tree polytope on 2-trees

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• Steiner's problem in graphs and its implications
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item