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

Voir la notice de l'article

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

[1] Alexander M. J., Robins G., “New Perfomance-Driven FPGA Routing Algorithms”, Proceedings of the 32nd annual ACM/IEEE Design Automation Conference, 1996, 562–567

[2] Chin L. L., Chuan Y. T., Lee R., “The Full Steiner Tree Problem in Phylogeny”, Computing and Combinatorics, 2002, 107–116 | MR | Zbl

[3] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Per. s angl. E. V. Levnera, M. A. Frumkina, ed. A. A. Fridman, Mir, M., 1982, 416 pp.

[4] Romanovskii I. V., Diskretnyi analiz, Nevskii Dialekt, SPb., 2003, 320 pp.

[5] Takahashi H., Matsuyama A., “An Approximate Solution for the Steiner Problem In Graphs”, Math. Japonica, 24:6 (1980), 573–577 | MR | Zbl

[6] Korman T., Leizerson Ch., Rivest R., Shtain K., Algoritmy. Postroenie i analiz, Per. s angl., ed. A. Shen, Vilyams, M., 2005, 1293 pp.

[7] 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

[8] Charikar M., “Approximation Algorithms for Directed Steiner Problems”, J. of Algorithms, 33:1 (1999), 73–91 | DOI | MR | Zbl