The Complexity of Computing Steiner Minimal Trees

Cited in

(only showing first 100 items - show all)

A linear time algorithm for full Steiner trees
Exact computation of Steiner minimal trees in the plane
Steiner minimal trees for regular polygons
Steiner minimal trees on sets of four points
A decomposition theorem on Euclidean Steiner minimal trees
The Steiner problem in phylogeny is NP-complete
Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time
The Steiner ratio conjecture for six points
Some upper bounds for minimal trees
A primer of the Euclidean Steiner problem
On Steiner ratio conjectures
Minimal length tree networks on the unit sphere
The role of Steiner hulls in the solution to Steiner tree problems
On graphs preserving rectilinear shortest paths in the presence of obstacles
A proof of the Gilbert-Pollak conjecture on the Steiner ratio
How to find Steiner minimal trees in Euclidean \(d\)-space
Graham's problem on shortest networks for points on a circle
Improved computation of plane Steiner minimal trees
Steiner minimal trees for a class of zigzag lines
Two new criteria for finding Steiner hulls in Steiner tree problems
A heuristic for Euclidean and rectilinear Steiner problems
The Steiner minimal network for convex configurations
Some remarks on the Steiner problem
Neural and delay based heuristics for the Steiner problem in networks
A neural network for the Steiner minimal tree problem
Some results on greedy algorithm conjectures
Steiner polygons in the Steiner problem
A continuous version of a result of Du and Hwang
On the Steiner ratio in 3-space
Full minimal Steiner trees on lattice sets
Cut and patch Steiner trees for ladders
The Steiner ratio for the dual normed plane
The computational complexity of Steiner tree problems in graded matrices
Non-crossing of plane minimal spanning and minimal T1 networks
The Steiner ratio of high-dimensional Banach--Minkowski spaces.
Bottleneck bichromatic full Steiner trees
Minimum rectilinear Steiner tree of n points in the unit square
The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
Minimum Steiner trees in normed planes
A class of full Steiner minimal trees
Steiner's problem in double trees
On greedy heuristic for Steiner minimum trees
On component-size bounded Steiner trees
A tight lower bound for the Steiner ratio in Minkowski planes
Steiner minimal trees in \(L^ 2_ p\)
Gradient-constrained minimum networks. III: Fixed topology
Smoothed analysis of partitioning algorithms for Euclidean functionals
On the structure and complexity of the 2-connected Steiner network problem in the plane
On the restricted 1-Steiner tree problem
On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\)
Insight into the computation of Steiner minimal trees in Euclidean space of general dimension
1-line minimum rectilinear Steiner trees and related problems
On the restricted k-Steiner tree problem
Approximation algorithms for solving the line-capacitated minimum Steiner tree problem
Mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in \(\mathbb{R}^d\)
On a nonconvex MINLP formulation of the Euclidean Steiner tree problem in \(n\)-space: missing proofs
The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
Geometric multicut: shortest fences for separating groups of objects in the plane
Computational complexity of the 2-connected Steiner network problem in the \(\ell_p\) plane
On the history of the Euclidean Steiner tree problem
Bottleneck Steiner tree with bounded number of Steiner vertices
Breakout local search for the Steiner tree problem with revenue, budget and hop constraints
The Euclidean bottleneck full Steiner tree problem
Probabilistic properties of topologies of minimal fillings of finite metric spaces
Variable neighbourhood search for the minimum labelling Steiner tree problem
A near linear time approximation scheme for Steiner tree among obstacles in the plane
Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
Isoperimetric enclosures
Monochromatic geometric k-factors for bicolored point sets with auxiliary points
Reducing the diameter of a unit disk graph via node addition
On the clustered Steiner tree problem
A Newton's method for perturbed second-order cone programs
Upper and lower bounds for the lengths of Steiner trees in 3-space
Approximation schemes for node-weighted geometric Steiner tree problems
Approximate Euclidean Steiner trees
Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\)
Euclidean Steiner trees optimal with respect to swapping 4-point subtrees
Complexity of Steiner tree in split graphs -- dichotomy results
An algorithm to find the link constrained Steiner tree in undirected graphs
An overview of exact algorithms for the Euclidean Steiner tree problem in n-space
Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions
On the clustered Steiner tree problem
THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD
Steiner tree problem with minimum number of Steiner points and bounded edge-length
On characteristic area of Steiner tree
A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in n-space
Using structured steiner trees for hierarchical global routing
Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints
(1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree
Steiner Minimal Trees on Zig-Zag Lines
Steiner Minimal Tree for Points on a Circle
scientific article; zbMATH DE number 3717342 (Why is no real title available?)
The 1-Steiner-Minimal-Tree problem in Minkowski-spaces
Determining shortest networks in the Euclidean plane
The local Steiner problem in normed planes
Growing Half-Balls: Minimizing Storage and Communication Costs in Content Delivery Networks
The saga of minimum spanning trees
A Lagrangean-based decomposition approach for the link constrained Steiner tree problem
The computation of nearly minimal Steiner trees in graphs
Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints

This page was built for publication: The Complexity of Computing Steiner Minimal Trees

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