Asymptotics of connectivity probabilities for pairs of graph nodes
For graphs with low reliable arcs, asymptotics of probabilities for connectivities between all pairs of nodes are constructed. Parameters of these asymptotics are characteristics of shortest paths in the graph. To calculate these characteristics, some modifications of classical algorithms are developed. On the base of these results, numerical experiment is realized. This experiment demonstrates advantages of suggested algorithms.
Download file
Counter downloads: 190
Keywords
кратчайший путь, вероятность связности, вычислительная сложность, shortest path, connectivity probability, computational complexityAuthors
| Name | Organization | |
| Tsitsiashvili G. Sh. | Institute of Applied Mathematics of Far Eastern Branch of the Russian Academy of Sciences (Vladivostok) | guram@iam.dvo.ru |
| Osipova M.A. | Institute of Applied Mathematics of Far Eastern Branch of the Russian Academy of Sciences (Vladivostok) | mao1975@list.ru |
| Losev A.S. | Institute of Applied Mathematics of Far Eastern Branch of the Russian Academy of Sciences (Vladivostok) | alexax@bk.ru |
References
