$k$-Clustering optimization algorithmfor Steiner problem in directed graphs

Steiner tree problem in directed graphs is 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$. New heuristic algorithm based on dividing graph into clusters and solving partial Steiner problems with exact algorithm is presented. Computational complexity is found and theorem is proven. Also computational experiments are provided.