Steiner Trees for Terminals Constrained to Curves

DOI10.1137/S0895480192241190zbMath0869.05023OpenAlexW2072431005MaRDI QIDQ3128200

Joachim Hyam Rubinstein, Doreen Anne Thomas, Nicholas C. Wormald

Publication date: 20 August 1997

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480192241190

zbMATH Keywords

polynomial time algorithmcurvesNP-hardEuclidean Steiner tree

Mathematics Subject Classification ID

Trees (05C05) Continuous location (90B85) Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD ⋮ A new second‐order conic optimization model for the Euclidean Steiner tree problem in Rd$\mathbb {R}^d$ ⋮ Directional derivative of the weight of a minimal filling in Riemannian manifolds ⋮ Unnamed Item ⋮ A polynomial algorithm for a constrained traveling salesman problem ⋮ On the history of the Euclidean Steiner tree problem ⋮ On the restricted 1-Steiner tree problem ⋮ An overview of exact algorithms for the Euclidean Steiner tree problem inn-space ⋮ Insight into the computation of Steiner minimal trees in Euclidean space of general dimension ⋮ On the restricted \(k\)-Steiner tree problem

This page was built for publication: Steiner Trees for Terminals Constrained to Curves