Geodesic
Heuristics for design of reliable telecommunication network
Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 164-165.

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

In this paper, the problem of finding a spanning $k$-tree of minimum weight in a complete weighted graph is considered. Such problem has a number of applications in designing reliable telecommunication networks. This problem is known to be NP-hard and generalizes a classical problem in graphs, the Minimum Spanning Tree Problem. For solving the problem, the following four effective heuristics are offered. The first heuristic is based on the idea of a well-known Prim's algorithm, the second one is based on a dynamic programming approach, and the other two use the idea of iterative improvement of a starting solution. Preliminary numerical experiment was performed to compare the effectiveness of the proposed algorithms with known heuristics and exact algorithms. Based on the results of the computational experiment, it follows that in order to solve such problem of small and medium dimension, it is advisable to use heuristics based on iterative improvement of a starting solution, and in order to solve the problem of high dimension it is advisable to use an algorithm based on dynamic programming approach, because it computes a solution with sufficient accuracy within reasonable computing time.
Keywords: spanning $k$-tree, invulnerable networks, NP-hard, heuristics. 
@article{PDMA_2014_7_a69,
     author = {R. E. Shangin},
     title = {Heuristics for design of reliable telecommunication network},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {164--165},
     publisher = {mathdoc},
     number = {7},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2014_7_a69/}
}
TY  - JOUR
AU  - R. E. Shangin
TI  - Heuristics for design of reliable telecommunication network
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2014
SP  - 164
EP  - 165
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2014_7_a69/
LA  - ru
ID  - PDMA_2014_7_a69
ER  - 
%0 Journal Article
%A R. E. Shangin
%T Heuristics for design of reliable telecommunication network
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2014
%P 164-165
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2014_7_a69/
%G ru
%F PDMA_2014_7_a69
R. E. Shangin. Heuristics for design of reliable telecommunication network. Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 164-165. http://geodesic.mathdoc.fr/item/PDMA_2014_7_a69/

[1] Farley A., “Networks immune to isolated failures”, Networks, 11 (1981), 255–268 | DOI | MR | Zbl

[2] Rose D., “On simple characterizations of $k$-trees”, Discr. Math., 7 (1974), 317–322 | DOI | MR | Zbl

[3] Prim R., “Shortest connection networks and some generalizations”, Bell Systems Techn. J., 36 (1957), 1389–1397 | DOI

[4] Bern M., Networks Design Problems: Steiner Trees and Spanning $k$-Trees, Ph. D. Thesis, University of Berkeley, 1987, 289 pp.

[5] Candia A., Bravo H., “A simulated annealing approach for minimum cost isolated failure immune networks”, Essays and Surveys in Metaheuristics, 15 (2002), 169–183 | DOI | MR | Zbl

[6] Beltran H., Skorin-Kapov D., “On minimum cost isolated failure immune network”, Telecommunication Systems, 3 (1994), 183–200 | DOI