On the structure and complexity of the 2-connected Steiner network problem in the plane

DOI10.1016/S0167-6377(99)00068-1zbMath0960.05039MaRDI QIDQ1977645

J. Scott Provan, Emily Larson Luebke

Publication date: 8 February 2001

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

designpolynomial approximationsurvivabilitySteiner treenetwork graphs

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

New pruning rules for the Steiner tree problem and 2-connected Steiner network problem ⋮ Bounding component sizes of two-connected Steiner networks ⋮ Fixed parameter tractability of a biconnected bottleneck Steiner network problem ⋮ The complexity landscape of disaster‐aware network extension problems ⋮ An exact algorithm for the bottleneck 2-connected \(k\)-Steiner network problem in \(L_p\) planes ⋮ Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane ⋮ Computing minimum 2‐edge‐connected Steiner networks in the Euclidean plane ⋮ Two-connected Steiner networks: structural properties ⋮ Relay placement for two-connectivity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum-weight two-connected spanning networks
• A linear time algorithm for full Steiner trees
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• The Steiner tree problem
• Minimal Steiner trees for rectangular arrays of lattice points
• On the Problem of Steiner
• Convexity and the Steiner tree problem
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• The Complexity of Computing Steiner Minimal Trees
• On shortest two-connected Steiner networks with Euclidean distance
• Hamilton Paths in Grid Graphs

This page was built for publication: On the structure and complexity of the 2-connected Steiner network problem in the plane