Generalized steiner problem in series-parallel networks

DOI10.1016/0196-6774(86)90018-0zbMath0623.94023OpenAlexW2090321732MaRDI QIDQ3762228

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

series-parallel graphlinear time algorithmsgeneralized Steiner problembiconnected subnetworkedge-biconnected subnetworkminimum cost subnetwork

Mathematics Subject Classification ID

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

Related Items (19)

Arborescence polytopes for series-parallel graphs ⋮ On perfectly two-edge connected graphs ⋮ The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs ⋮ On finding two-connected subgraphs in planar graphs ⋮ A PTAS for weight constrained Steiner trees in series--parallel graphs. ⋮ Box-total dual integrality and edge-connectivity ⋮ 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 ⋮ Network Resilience ⋮ Problems with generalized Steiner problems ⋮ Linear bounds for on-line 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 ⋮ The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation ⋮ Low-connectivity network design on series-parallel graphs ⋮ Critical extreme points of the 2-edge connected spanning subgraph polytope ⋮ Steiner's problem in double trees ⋮ The Steiner tree polytope and related polyhedra

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