|
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
Abstract:
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, distance, distance matrix, metric ball, number of balls, diversity vector of balls, algorithm, complexity.
Received February 18, 2016, published March 3, 2016
Citation:
T. I. Fedoryaeva, “Computing the diversity vectors of balls of a given graph”, Sib. Èlektron. Mat. Izv., 13 (2016), 122–129
Linking options:
https://www.mathnet.ru/eng/semr660 https://www.mathnet.ru/eng/semr/v13/p122
|
Statistics & downloads: |
Abstract page: | 276 | Full-text PDF : | 49 | References: | 62 |
|