Steiner Trees for Terminals Constrained to Curves

DOI10.1137/S0895480192241190MaRDI QIDQ3128200zbMATH OpenOpenAlexFDO

Authors J. Hyam Rubinstein, D. A. Thomas, Nicholas 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

NP-hardpolynomial time algorithmcurvesEuclidean Steiner tree

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1286271
• Steiner trees on curved surfaces
• Steiner trees and convex geometries
• Constrained Steiner trees in Halin graphs
• scientific article; zbMATH DE number 1163707
• The Steiner tree problem for terminals on the boundary of a rectilinear polygon
• Computing and Combinatorics
• Algorithms for terminal Steiner trees
• A note on the terminal Steiner tree problem
• Diameter-constrained Steiner trees

Cited in

(20)

• Efficient algorithms for Euclidean Steiner minimal tree on near-convex terminal sets
• On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)
• Steiner trees with infinitely many terminals on the sides of an angle
• Computing Euclidean Steiner trees over segments
• Insight into the computation of Steiner minimal trees in Euclidean space of general dimension
• On the history of the Euclidean Steiner tree problem
• Fully dynamic algorithms for Euclidean Steiner tree
• On the restricted 1-Steiner tree problem
• On the restricted k-Steiner tree problem
• Angle-Restricted Steiner Arborescences for Flow Map Layout
• A polynomial algorithm for a constrained traveling salesman problem
• 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$
• Convexity and the Steiner tree problem
• scientific article; zbMATH DE number 1286271 (Why is no real title available?)
• scientific article; zbMATH DE number 1424546 (Why is no real title available?)
• Approximate Euclidean Steiner trees
• Mathematical optimization models for the Euclidean Steiner tree problem in \(\mathbb{R}^d\)
• Directional derivative of the weight of a minimal filling in Riemannian manifolds
• An overview of exact algorithms for the Euclidean Steiner tree problem in n-space

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

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