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

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

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



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






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


Вестник Тверского государственного университета. Серия: Прикладная математика, 2018, выпуск 2, страницы 85–98
DOI: https://doi.org/10.26456/vtpmk496
(Mi vtpmk496)
 

Теоретические основы информатики

Равномерная поуровневая укладка графов

Б. Н. Карлов, А. В. Наймушин

Тверской государственный университет, г. Тверь
Список литературы:
Аннотация: В статье рассматривается алгоритм поуровневой укладки ациклических ориентированных графов. Предложен метод для распределения вершин графа по уровням, при котором вершины пути укладываются на уровни с приблизительно равным шагом. Описанный алгоритм сначала распределяет по уровням вершины, лежащие на самых длинных путях графа. После этого алгоритм укладывает на эти же уровни оставшиеся вершины, при этом еще не уложенные пути перебираются по убыванию длины. Для нахождения еще не уложенных длинных путей используется модифицированный метод поиска путей в ациклических графах, основанный на поиске в глубину и топологической сортировке. Доказано, что временная сложность описанного алгоритма при работе на графе $G=(V,E)$ составляет $O(|V||E|)$. Были проведены вычислительные эксперименты, которые показали, что для графов не очень большого размера с относительно маленькой плотностью время работы алгоритма является приемлемым для практического использования.
Ключевые слова: укладка графа на плоскость, распределение вершин по уровням, алгоритм Сугиямы, временная сложность.
Поступила в редакцию: 28.05.2018
Исправленный вариант: 22.06.2018
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.173.2
Образец цитирования: Б. Н. Карлов, А. В. Наймушин, “Равномерная поуровневая укладка графов”, Вестник ТвГУ. Серия: Прикладная математика, 2018, № 2, 85–98
Цитирование в формате AMSBIB
\RBibitem{KarNai18}
\by Б.~Н.~Карлов, А.~В.~Наймушин
\paper Равномерная поуровневая укладка графов
\jour Вестник ТвГУ. Серия: Прикладная математика
\yr 2018
\issue 2
\pages 85--98
\mathnet{http://mi.mathnet.ru/vtpmk496}
\crossref{https://doi.org/10.26456/vtpmk496}
\elib{https://elibrary.ru/item.asp?id=35171197}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/vtpmk496
  • https://www.mathnet.ru/rus/vtpmk/y2018/i2/p85
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Вестник Тверского государственного университета. Серия: Прикладная математика
    Статистика просмотров:
    Страница аннотации:261
    PDF полного текста:229
    Список литературы:32
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024