Faster algorithm for optimum Steiner trees

We present a new deterministic algorithm for the Steiner tree problem in weighted graphs. Its running time is O(nk2k+(log2k)(log2n))O(nk2k+(log2k)(log2n)), where n is the number of vertices and k   is the number of terminals. This is faster than all previously known algorithms if logn(loglogn)3

► New exact algorithm for the Steiner tree problem in weighted graphs.
► Faster than previous algorithms for moderate number of terminals.
► Based on dynamic programming and a new tree composition theorem.