Sib. Èlektron. Mat. Izv., 2016, Volume 13, Pages 122–129
This article is cited in 1 scientific paper (total in 1 paper)
Discrete mathematics and mathematical cybernetics
Computing the diversity vectors of balls of a given graph
T. I. Fedoryaeva
Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
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.
graph, distance, distance matrix, metric ball, number of balls, diversity vector of balls, algorithm, complexity.
PDF file (153 kB)
Received February 18, 2016, published March 3, 2016
T. I. Fedoryaeva, “Computing the diversity vectors of balls of a given graph”, Sib. Èlektron. Mat. Izv., 13 (2016), 122–129
Citation in format AMSBIB
\paper Computing the diversity vectors of balls of a given graph
\jour Sib. \`Elektron. Mat. Izv.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
T. I. Fedoryaeva, “Stroenie vektora raznoobraziya sharov tipichnogo grafa zadannogo diametra”, Sib. elektron. matem. izv., 13 (2016), 375–387
|Number of views:|