|
Теоретические основы информатики
Равномерная поуровневая укладка графов
Б. Н. Карлов, А. В. Наймушин Тверской государственный университет, г. Тверь
Аннотация:
В статье рассматривается алгоритм поуровневой укладки ациклических ориентированных графов. Предложен метод для распределения вершин графа по уровням, при котором вершины пути укладываются на уровни с приблизительно равным шагом. Описанный алгоритм сначала распределяет по уровням вершины, лежащие на самых длинных путях графа. После этого алгоритм укладывает на эти же уровни оставшиеся вершины, при этом еще не уложенные пути перебираются по убыванию длины. Для нахождения еще не уложенных длинных путей используется модифицированный метод поиска путей в ациклических графах, основанный на поиске в глубину и топологической сортировке. Доказано, что временная сложность описанного алгоритма при работе на графе $G=(V,E)$ составляет $O(|V||E|)$. Были проведены вычислительные эксперименты, которые показали, что для графов не очень большого размера с относительно маленькой плотностью время работы алгоритма является приемлемым для практического использования.
Ключевые слова:
укладка графа на плоскость, распределение вершин по уровням, алгоритм Сугиямы, временная сложность.
Поступила в редакцию: 28.05.2018 Исправленный вариант: 22.06.2018
Образец цитирования:
Б. Н. Карлов, А. В. Наймушин, “Равномерная поуровневая укладка графов”, Вестник ТвГУ. Серия: Прикладная математика, 2018, № 2, 85–98
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vtpmk496 https://www.mathnet.ru/rus/vtpmk/y2018/i2/p85
|
Статистика просмотров: |
Страница аннотации: | 261 | PDF полного текста: | 229 | Список литературы: | 32 |
|