Визуализация кооперативных схем: гибридный эвристический алгоритм для минимизации количества пересечений ребер при укладке графа
Автор: Васильев Юрий Михайлович, Фридман Григорий Морицович
Журнал: Известия Санкт-Петербургского государственного экономического университета @izvestia-spgeu
Рубрика: Методология и инструментарий управления
Статья в выпуске: 1-2 (103), 2017 года.
Бесплатный доступ
В статье предложен новый метод (гибридный алгоритм) для минимизации пересечений ребер иерархического графа посредством определения порядка расположения вершин на его слоях, с учетом верхней границы по времени счета. Проведены массовые расчеты, которые продемонстрировали существенное снижение числа пересечений ребер графов с широким набором характеристик.
Направленный иерархический ациклический граф, число пересечений ребер графа, эвристические методы, кластеризация
Короткий адрес: https://sciup.org/14875816
IDR: 14875816
Список литературы Визуализация кооперативных схем: гибридный эвристический алгоритм для минимизации количества пересечений ребер при укладке графа
- Battista G.D., Gard A., Liotta G., Tamassia R., Tassinari E., Vargiu F. An experimental comparison of four graph drawing algorithms//Computational Geometry. 1997. Vol. 7. P. 303-325.
- Sugiyama K. Graph drawing and applications for software and knowledge engineers//World Scientific, series on software engineering and knowledge engineering. 2002. Vol. 11.
- Michalak K., Korzczak J. Graph mining approach to suspicious transaction detection//Proceedings of the Federated Conference on Computer Science and Information Systems, 2011. P. 69-75.
- Федеральный закон «О внесении изменений в Федеральный закон «О государственном оборонном заказе» и отдельные законодательные акты Российской Федерации» от 29.06.2015 г. № 159-ФЗ.
- Sugiyama K., Tagawa S., TodaM. Methods for visual undertanding of hierarchical systems//IEEE Transactions on Systems, Man, and Cybernetics. 1981. Vol. SMC-11. № 2. Р. 109-125.
- Апанович З.В. Методы навигации при визуализации графов//Вестник НГУ, серия: Информационные технологии. 2008. Том 6, вып. 3. С. 35-47.
- Healy P., Nikolov N.S. Hierarchical drawing algorithms//Handbook of Graph Drawing and Visualization. 2005. Vol. 1, chapter 13. Р. 409-454.
- Eades P., Kelly D. Heurisitcs for reducing crossings in 2-layered networks//Ars Combin. 1986. Vol. 21. Р. 89-98.
- Junger M., Mutzel P. Two-layer straightline crossing minimization: performance of exact and heuristic algorithms//Journal of graph algorithms and applications. 1997. Vol. 1. Р. 1-25.
- Бабурин Д.Е. Иерархический подход для автоматического размещения ациклических графов//Современные проблемы конструирования программ, 2002. С. 7-37.
- Alaa A.K. Ismaeel. Dynamic Drawing of Hierarchical Graphs//PHD thesis, Karlsruher InstitutsTechnologie, 2012.
- Gansner E.R., Koutsofios E., North S.C., Vo K.-P. A technique for drawing directed graphs//At&T Bell Laboratories. 1993. Vol. 19. Р. 214-230.
