| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427777 | Information Processing Letters | 2011 | 5 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jens Vygen,