Geodesic
$k$-Clustering optimization algorithmfor Steiner problem in directed graphs
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 2 (2011), pp. 29-39

Voir la notice de l'article provenant de la source Math-Net.Ru

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
Mots-clés : heuristic algorithm. 
@article{VSPUI_2011_2_a3,
     author = {D. A. Eibozhenko},
     title = {$k${-Clustering} optimization algorithmfor {Steiner} problem in directed graphs},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {29--39},
     publisher = {mathdoc},
     number = {2},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2011_2_a3/}
}
TY  - JOUR
AU  - D. A. Eibozhenko
TI  - $k$-Clustering optimization algorithmfor Steiner problem in directed graphs
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2011
SP  - 29
EP  - 39
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2011_2_a3/
LA  - ru
ID  - VSPUI_2011_2_a3
ER  - 
%0 Journal Article
%A D. A. Eibozhenko
%T $k$-Clustering optimization algorithmfor Steiner problem in directed graphs
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2011
%P 29-39
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VSPUI_2011_2_a3/
%G ru
%F VSPUI_2011_2_a3
D. A. Eibozhenko. $k$-Clustering optimization algorithmfor Steiner problem in directed graphs. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 2 (2011), pp. 29-39. http://geodesic.mathdoc.fr/item/VSPUI_2011_2_a3/