Generalized steiner problem in series-parallel networks

DOI10.1016/0196-6774(86)90018-0MaRDI QIDQ3762228zbMATH OpenOpenAlexFDO

Authors Pawel Winter

Publication date 1986

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(86)90018-0

zbMATH Keywords

biconnected subnetworkedge-biconnected subnetworkgeneralized Steiner problemlinear time algorithmsminimum cost subnetworkseries-parallel graph

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Generalized Steiner problem in outerplanar networks
• Steiner problem in networks: A survey
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Publication:4945799
• On Steiner versions of (bi)connectivity in network problems

Cited in

(37)

• Generalized Steiner problem in outerplanar networks
• Problems with generalized Steiner problems
• Minimal cost linkages in graphs
• The Steiner tree polytope and related polyhedra
• Arborescence polytopes for series-parallel graphs
• On perfectly two-edge connected graphs
• On finding two-connected subgraphs in planar graphs
• A PTAS for weight constrained Steiner trees in series--parallel graphs.
• On survivable network polyhedra
• Two variations of the minimum Steiner problem
• Steiner's problem in double trees
• On Steiner versions of (bi)connectivity in network problems
• The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs
• A 2-approximation algorithm and beyond for the minimum diameter k-Steiner forest problem
• Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
• The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation
• Critical extreme points of the 2-edge connected spanning subgraph polytope
• Box-total dual integrality and edge-connectivity
• Steiner networks with unicyclic connected components
• On the Steiner 2-edge connected subgraph polytope
• An efficiently solvable case of the minimum weight equivalent subgraph problem
• On multiple steiner subgraph problems
• Network Resilience
• Bottleneck Steiner Subnetwork Problems with k-Connectivity Constraints
• Low-connectivity network design on series-parallel graphs
• scientific article; zbMATH DE number 1796994 (Why is no real title available?)
• The generalized Steiner cable-trench problem with application to error correction in vascular image analysis
• scientific article; zbMATH DE number 841993 (Why is no real title available?)
• scientific article; zbMATH DE number 1424550 (Why is no real title available?)
• Parallelism in Steiner systems
• On the dominant of the Steiner 2-edge connected subgraph polytope
• Design of survivable networks with low connectivity requirements
• Linear bounds for on-line Steiner problems
• Extended formulation and branch-and-cut-and-price algorithm for the two connected subgraph problem with disjunctive constraints
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A factoring approach for the Steiner tree problem in undirected networks
• The Steiner forest problem revisited

This page was built for publication: Generalized steiner problem in series-parallel networks

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