Geodesic
Computing the diversity vectors of balls of a given graph
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 122-129.

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

For an ordinary finite not necessarily connected graph, the diversity vector of balls ($i$th component of the vector is equal to the number of different balls of radius i) is studied. Properties of metric balls in such graphs are established. In particular, a coincidence condition of balls with centers at different vertices is found. Based on these properties, the algorithm of computing the diversity vector of balls of a given graph $G=(V,E)$ with a running time $O(|V|^3)$ is developed.
Keywords: graph, metric ball, number of balls, diversity vector of balls, algorithm, complexity.
Mots-clés : distance, distance matrix 
@article{SEMR_2016_13_a56,
     author = {T. I. Fedoryaeva},
     title = {Computing the diversity vectors of balls of a given graph},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {122--129},
     publisher = {mathdoc},
     volume = {13},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2016_13_a56/}
}
TY  - JOUR
AU  - T. I. Fedoryaeva
TI  - Computing the diversity vectors of balls of a given graph
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2016
SP  - 122
EP  - 129
VL  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2016_13_a56/
LA  - ru
ID  - SEMR_2016_13_a56
ER  - 
%0 Journal Article
%A T. I. Fedoryaeva
%T Computing the diversity vectors of balls of a given graph
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2016
%P 122-129
%V 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2016_13_a56/
%G ru
%F SEMR_2016_13_a56
T. I. Fedoryaeva. Computing the diversity vectors of balls of a given graph. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 122-129. http://geodesic.mathdoc.fr/item/SEMR_2016_13_a56/

[1] T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, Cambridge, 2009 | MR | Zbl

[2] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994

[3] Sibirsk. Zhur. Issled. Oper., 1:1 (1994), 5–12 | MR | Zbl

[4] Diskretn. Anal. Issled. Oper., 21:1 (2014), 44–52 | DOI | MR | Zbl

[5] T. I. Fedoryaeva, “Diversity of balls in the metric spaces of trees”, Diskretn. Anal. Issled. Oper., 12:3 (2005), 74–84 | MR | Zbl

[6] Diskretn. Anal. Issled. Oper., 14:2 (2007), 47–67 | DOI | MR | Zbl

[7] T. I. Fedoryaeva, “Exact upper estimates of the number of different balls of given radius in graphs with fixed number of vertices and diameter”, Diskretn. Anal. Issled. Oper., 16:6 (2009), 74–92 | MR | Zbl

[8] Diskretn. Anal. Issled. Oper., 17:1 (2010), 65–74 | DOI | MR | Zbl

[9] T. I. Fedoryaeva, Combinatorial algorithms, Izd. NGU, Novosibirsk, 2011

[10] Diskretn. Anal. Issled. Oper., 20:1 (2013), 58–76 | DOI | MR | Zbl

[11] T. I. Fedoryaeva, “The diversity vector of balls of a typical graph of small diameter”, Diskretn. Anal. Issled. Oper., 22:6 (2015), 43–54 | MR

[12] F. Harary, Graph Theory, Addison-Wesley, London, 1969 | MR | Zbl

[13] E. M. Reingold, J. Nievergelt, N. Deo, Combinatorial algorithms: theory and practice, Prentice-Hall, Englewood Cliffs, NJ, 1977 | MR

[14] Diskretn. Anal. Issled. Oper., 13:1 (2006), 99–108 | DOI | MR | MR | Zbl