Uniform graph layering
Борис Николаевич Карлов, Alexey Naimushin · Herald of Tver State University Series Applied Mathematics · 2018
В статье рассматривается алгоритм поуровневой укладки ациклических ориентированных графов.Предложен метод для распределения вершин графа по уровням, при котором вершины пути укладываются на уровни с приблизительно равным шагом.Описанный алгоритм сначала распределяет по уровням вершины, лежащие на самых длинных путях графа.После этого алгоритм укладывает на эти же уровни оставшиеся вершины, при этом еще не уложенные пути перебираются по убыванию длины.Для нахождения еще не уложенных длинных путей используется модифицированный метод поиска путей в ациклических графах, основанный на поиске в глубину и топологической сортировке.Доказано, что временная сложность описанного алгоритма при работе на графе 𝐺 = (𝑉, 𝐸) составляет 𝑂(|𝑉 ||𝐸|).Были проведены вычислительные эксперименты, которые показали, что для графов не очень большого размера с относительно маленькой плотностью время работы алгоритма является приемлемым для практического использования.