RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


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

Эта публикация цитируется в 1 научной статье (всего в 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.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 14-01-00507_а
Работа поддержана РФФИ (грант 14-01-00507).


DOI: https://doi.org/10.17377/semi.2016.13.010

Полный текст: PDF файл (153 kB)
Список литературы: PDF файл   HTML файл

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

Тип публикации: Статья
УДК: 519.173+519.178
MSC: 05C12+05C85
Поступила 18 февраля 2016 г., опубликована 3 марта 2016 г.

Образец цитирования: Т. И. Федоряева, “Вычисление вектора разнообразия шаров заданного графа”, Сиб. электрон. матем. изв., 13 (2016), 122–129

Цитирование в формате AMSBIB
\RBibitem{Fed16}
\by Т.~И.~Федоряева
\paper Вычисление вектора разнообразия шаров заданного графа
\jour Сиб. электрон. матем. изв.
\yr 2016
\vol 13
\pages 122--129
\mathnet{http://mi.mathnet.ru/semr660}
\crossref{https://doi.org/10.17377/semi.2016.13.010}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr660
  • http://mi.mathnet.ru/rus/semr/v13/p122

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Т. И. Федоряева, “Строение вектора разнообразия шаров типичного графа заданного диаметра”, Сиб. электрон. матем. изв., 13 (2016), 375–387  mathnet  crossref
  • Просмотров:
    Эта страница:123
    Полный текст:22
    Литература:34

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019