Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane

DOI10.1016/J.TCS.2020.11.002zbMath1464.68296OpenAlexW3097342811MaRDI QIDQ2216434

Doreen Anne Thomas, Marcus Brazil, Charl J. Ras

Publication date: 16 December 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.11.002

zbMATH Keywords

NP-completenessnormed plane2-connectedSteiner network

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum-weight two-connected spanning networks
• On Steiner minimal trees with \(L_ p\) distance
• On shortest three-edge-connected Steiner networks with Euclidean distance
• On minimum-weight \(k\)-edge connected Steiner networks on metric spaces
• Minimum Steiner trees in normed planes
• The Fermat--Torricelli problem in normed planes and spaces
• Paired calibrations applied to soap films, immiscible fluids, and surfaces or networks minimizing other norms
• On the structure and complexity of the 2-connected Steiner network problem in the plane
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• Bounding component sizes of two-connected Steiner networks
• The Steiner ratio Gilbert-Pollak conjecture is still open
• Two-connected Steiner networks: structural properties
• The Complexity of Computing Steiner Minimal Trees
• Design of Survivable Networks: A survey
• A textbook of graph theory

This page was built for publication: Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane