Geodesic
Approximation algorithm $S^*$ for Steiner problem in Euclidean directed graphs
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 3 (2012), pp. 23-32

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

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