RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2016, том 13, страницы 122–129 (Mi semr660)

Эта публикация цитируется в 1 статье

Дискретная математика и математическая кибернетика

Вычисление вектора разнообразия шаров заданного графа

Т. И. Федоряева

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.

УДК: 519.173+519.178

MSC: 05C12+05C85

Поступила 18 февраля 2016 г., опубликована 3 марта 2016 г.

DOI: 10.17377/semi.2016.13.010



Реферативные базы данных:


© МИАН, 2024