Applied mathematics

Approximation algorithm $S^*$ for Steiner problem in Euclidean directed graphs

D. A. Eibozhenko

St. Petersburg State University, Department of Mathematics and Mechanics

Abstract: Steiner tree problem in directed graphs is the most general in family of Steiner tree problems. Given a graph $G(M,N)$, specified root $b$ in $M$ and subset $E$ of $M$, the task is to find minimum-cost arborescence at $G$, rooted at $b$ and spanning all vertices in $E$. Many practical problems can be formalized using Euclidean graph. A new method using data of vertices position on plane for constructing approximation solution is presented. The theorem of polynomial computational complexity of the method is provided. The comparison against other well-known approximation methods is shown.

Keywords: Steiner tree problem, NP-hard, dynamic programming, heuristic algorithm, Euclidean graph.

UDC: 519.176


Accepted: April 26, 2012