This article is cited in 1 paper

Applied mathematics

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

D. A. Eibozhenko

St. Petersburg State University, Department of Mathematics and Mechanics

Abstract: 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.

Keywords: Steiner tree problem, NP-complete, dynamic programming, heuristic algorithm.

UDC: 519.176


Accepted: December 16, 2010