So I would like to know what the fastest (asymptotically, worst case runtime) exact algorithm for the Euclidean Steiner tree problem is. (More precisely, I would like to know the best known algorithm and runtime bound pair.)
Searching the Web, I found:
- A 2010 "survey" on algorithms for the euclidean Steiner tree problem, which however seems a bit short for such an extensively researched topic and also does not seem to focus on asymptotic worst case runtimes.
- A more extensive and slightly newer 2013 survey that however seems to be mostly concerned with approximation algorithms with good constant approximation ratios.
- A quite recent 2020 Article on approaches for the Euclidean Steiner tree problem, which however focuses more on the currently considered approaches than on the best runtimes.
However, I didn't find any recent enough survey on the fastest (asymptotically, worst case) algorithms for the Euclidean Steiner tree problem, which is strange because the problem seems to be well studied, so I'm asking this question here.
By Euclidean Steiner tree problem, I mean the problem of finding a Steiner tree in the plane, with all points in the plane allowed as nonterminals.