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

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

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



Труды ИСП РАН:
Год:
Том:
Выпуск:
Страница:
Найти






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


Труды ИСП РАН, 2017, том 29, выпуск 2, страницы 7–26 (Mi tisp209)  

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

Размер памяти для хранения упорядоченного корневого графа

И. Б. Бурдонов, А. С. Косачев

Институт системного программирования РАН

Аннотация: В статье рассматривается размер памяти, необходимый и достаточный для хранения графа из класса неориентированных корневых упорядоченных связных графов как нумерованных, так и ненумерованных. Введение содержит основные определения и постановку задачи. Граф корневой, если одна из вершин выделена и названа корнем. Граф упорядоченный, если для каждой вершины все инцидентные ей рёбра линейно упорядочены. Граф нумерованный, если все его вершины помечены различными идентификаторами, в частности, пронумерованы целыми числами от $0$ до $n-1$, где $n$ — число вершин графа. Два неориентированных корневых упорядоченных графа $G$ и $G'$ считаются слабо изоморфными, если существует взаимно-однозначное соответствие вершин такое, что: 1) соответствующие вершины имеют одинаковые степени, 2) рёбра $ab$ из графа $G$ и $a'b'$ из графа $G'$, инцидентные соответствующим вершинам $a$ и $a'$ и имеющие в этих вершинах одинаковые номера, ведут в соответствующие вершины $b$ и $b'$, 3) корни соответствуют друг другу. Для нумерованных графов при изоморфизме дополнительно требуется совпадение номеров соответствующих вершин. Графы рассматриваются с точностью до слабого изоморфизма. Показано, что память, необходимая и достаточная для хранения любого графа из указанного класса, имеет размер $\Theta(m\log n)$ для нумерованных графов, $\Theta(n+(m-n+1)\log n)$ для ненумерованных графов с числом вершин $n$ и числом рёбер $m$, и $\Theta(n^2\log n)$ для графов без кратных рёбер и петель с числом вершин $n$. Также показано, что память, достаточная для хранения последовательности рёбер длины $O(n)$ или остова графа, имеет размер $O(n\log(n\Delta))$ или $O(n\log \Delta)$, соответственно, где $\Delta$ — максимальная степень вершины.

Ключевые слова: неориентированный граф, упорядоченный граф, нумерованный граф, корневой граф, представление графа, перечисление графов.

DOI: https://doi.org/10.15514/ISPRAS-2017-29(2)-1

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

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

Тип публикации: Статья

Образец цитирования: И. Б. Бурдонов, А. С. Косачев, “Размер памяти для хранения упорядоченного корневого графа”, Труды ИСП РАН, 29:2 (2017), 7–26

Цитирование в формате AMSBIB
\RBibitem{BurKos17}
\by И.~Б.~Бурдонов, А.~С.~Косачев
\paper Размер памяти для хранения упорядоченного корневого графа
\jour Труды ИСП РАН
\yr 2017
\vol 29
\issue 2
\pages 7--26
\mathnet{http://mi.mathnet.ru/tisp209}
\crossref{https://doi.org/10.15514/ISPRAS-2017-29(2)-1}
\elib{http://elibrary.ru/item.asp?id=29118076}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tisp209
  • http://mi.mathnet.ru/rus/tisp/v29/i2/p7

    ОТПРАВИТЬ: 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. Игорь Бурдонов, Александр Косачев, Александр Сортов, “Распределённые алгоритмы на корневых неориентированных графах”, Труды ИСП РАН, 29:5 (2017), 283–310  mathnet  crossref  elib
    2. И. Б. Бурдонов, А. С. Косачев, “Общий подход к решению задач на графах коллективом автоматов”, Труды ИСП РАН, 29:2 (2017), 27–76  mathnet  crossref  elib
    3. И. Б. Бурдонов, А. С. Косачев, “Проблема отката в ориентированной распределенной системе”, Труды ИСП РАН, 30:2 (2018), 167–194  mathnet  crossref  elib
  • Труды института системного программирования РАН
    Просмотров:
    Эта страница:89
    Полный текст:30
    Литература:18
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020