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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2012},
     number = {3},
     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
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
%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/

[1] Garey Michael R., Johnson David S., Computer and intractability

[2] Alexander M. J., Robins G., “New perfomance-driven FPGA routing algorithms”, Proc. of the 32nd annual ACM/IEEE Design Automation Conference, 1996, 562–567

[3] Chin L. L., Chuan Y. T., Lee R., “The full Steiner tree problem in phylogeny”, Computing and Combinatorics, 2002, 107–116 | MR | Zbl

[4] Chen C., Selective multicast communication in distributed systems, tech. report, University of Maryland, Maryland, 1992, 20 pp.

[5] Eibozhenko D. A., “Algoritm $k$-klasternoi optimizatsii dlya zadachi Shteinera na orientirovannykh grafakh”, Vestn. S.-Peterb. un-ta. Ser. 10: Prikladnaya matematika, informatika, protsessy upravleniya, 2011, no. 2, 29–39

[6] Dijkstra E. W., “A note on two problems in connexion with graphs”, Numerische Mathematik, 1 (1959), 269–271 | DOI | MR | Zbl

[7] Hart P. E., Nilsson N. J., Raphael B., “A formal basis for the heuristic determination of minimum cost paths”, IEEE transactions on Systems Science and Cybernetics, 4 (1968), 100–107 | DOI

[8] Romanovskii I. V., Eibozhenko D. A., “Modifikatsii metoda dinamicheskogo programmirovaniya v zadachakh Shteinera na orientirovannykh grafakh”, Kompyuternye instrumenty v obrazovanii, 2010, no. 5, 22–28

[9] Takahashi H., Matsuyama A., “An approximate solution for the Steiner problem in graphs”, Math. Japonica, 24:6 (1980), 573–577 | MR | Zbl

[10] Zelikovsky A., “11/6-approximation algorithm for the Steiner problem on graphs”, Proc. Fourth Czechoslovakian Symposium on Combinatorics, Graphs, and Complexity, 1992, 351–354 | DOI | MR | Zbl