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/