Geodesic
Asymptotics for connectivity probability of graph with low reliable arcs
Prikladnaâ diskretnaâ matematika, no. 1 (2013), pp. 93-98.

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

Asymptotics of connectivity probabilities for complete graphs with the low reliable arcs and for all pairs of nodes in them are constructed. Parameters of these asymptotics are characteristics of spanning trees and shortest paths. The calculation of the spanning trees characteristics is based on the Kirchhoff–Trent theorem. Modifications of classical algorithms are applied to calculate the characteristics of shortest paths.
Keywords: spanning tree, Kirchhoff's matrix, shortest path, connectivity probability, calculation complexity. 
@article{PDM_2013_1_a7,
     author = {G. Sh. Tsitsiashvili and M. A. Osipova and A. S. Losev},
     title = {Asymptotics for connectivity probability of graph with low reliable arcs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {93--98},
     publisher = {mathdoc},
     number = {1},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_1_a7/}
}
TY  - JOUR
AU  - G. Sh. Tsitsiashvili
AU  - M. A. Osipova
AU  - A. S. Losev
TI  - Asymptotics for connectivity probability of graph with low reliable arcs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 93
EP  - 98
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_1_a7/
LA  - ru
ID  - PDM_2013_1_a7
ER  - 
%0 Journal Article
%A G. Sh. Tsitsiashvili
%A M. A. Osipova
%A A. S. Losev
%T Asymptotics for connectivity probability of graph with low reliable arcs
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 93-98
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_1_a7/
%G ru
%F PDM_2013_1_a7
G. Sh. Tsitsiashvili; M. A. Osipova; A. S. Losev. Asymptotics for connectivity probability of graph with low reliable arcs. Prikladnaâ diskretnaâ matematika, no. 1 (2013), pp. 93-98. http://geodesic.mathdoc.fr/item/PDM_2013_1_a7/

[1] Tsitsiashvili G. Sh., “Complete calculation of disconnection probability in planar graphs”, Reliability: Theory and Applications, 1:1 (2012), 154–159 | MR

[2] Burtin Yu., Pittel B., “Asimptoticheskie otsenki nadezhnosti slozhnykh sistem”, Tekhnicheskaya kibernetika, 10:3 (1972), 90–96 | Zbl

[3] Whithney H., “Nonseparable and planar graphs”, Transact. Amer. Math. Soc., 34 (1932), 339–369 | DOI

[4] Kharari F., Teoriya grafov, Mir, M., 1973, 314 pp.

[5] Migov D. A., “Raschet nadezhnosti seti s ogranicheniem na diametr s primeneniem tochek sochleneniya”, Avtomatika i telemekhanika, 2011, no. 7, 69–74

[6] Migov D. A., “Raschet nadezhnosti seti s ogranicheniem na diametr s ispolzovaniem sochlenenii”, Problemy informatiki, 2011, no. 3, 4–9

[7] Raigorodskii A. M., “Modeli sluchainykh grafov i ikh primenenie”, Trudy MFTI, 2:4 (2010), 130–140 | Zbl

[8] Lomonosov M. V., Polesskii V. P., “Nizhnyaya otsenka nadezhnosti setei”, Problemy peredachi informatsii, 8:2 (1972), 47–53 | MR | Zbl

[9] Chebotarev P. Yu., Shamis E. V., “Matrichnaya teorema o lesakh i izmerenie svyazei v malykh sotsialnykh gruppakh”, Avtomatika i telemekhanika, 9 (1997), 125–137 | Zbl

[10] Ilin V. A., Poznyak E. G., Lineinaya algebra, Fizmatlit, M., 2004, 280 pp.

[11] Floid R. W., Steinberg L., “An adaptive algorithm for spatial grayscale”, SID 75 Digest, Lewis Winner, New York, N.Y., 1975, 36–37

[12] Kormen T., Leizerson Ch., Rivest R., Algoritmy: postroenie i analiz, MTsNMO, M., 2000, 893 pp.