Exact mathematical formulation for hyperedges portrayal of two-layer hypergraph in coopertion scheme

  • Юрий Михайлович Васильев Saint-Petersburg State University of Economics
Keywords: directed acyclic hierarchical graph, two-layer graph, hypergraph, hyperedge, orthogonal hyperedge portrayal, drawing graph, branch and bound method

Abstract

Цель: решение задачи минимизации пересечения гиперребер при укладке двухслойного гиперграфа в точной постановке. Обсуждение: прорисовка ребер – заключительный этап метода Сугиямы для укладки направленного ациклического иерархического графа. В диаграммах потоков финансовых данных и схемах кооперации контрагентов при выполнении государственных и коммерческих проектов ребра обычно прорисовывают вертикальными или горизонтальными сегментами. При этом сам иерархический граф рассматривается как иерархический гиперграф, который отличается от обычного графа тем, что его ребра соединяют не две вершины различных слоев, а некоторое множество вершин (предков) верхнего слоя с некоторым множеством вершин (потомков) расположенных в нижних слоях. Для прорисовки гиперребер исходный гиперграф представляется в виде множества двухслойных подграфов, состоящих из двух соседних слоев, и задача визуализации гиперребер решается для каждого подграфа отдельно. Результаты: дана точная математическая постановка задачи минимизации пересечений гиперребер для представленных требований к прорисовке двухслойного гиперграфа, получены и проанализированы числовые результаты решения сформулированной задачи методом ветвей и границ.

Downloads

Download data is not yet available.
Published
2017-02-20
How to Cite
Васильев, Ю. М. (2017). Exact mathematical formulation for hyperedges portrayal of two-layer hypergraph in coopertion scheme. Modern Economics: Problems and Solutions, 1, 8-21. https://doi.org/10.17308/meps.2017.1/1589
Section
Mathematical Methods in Economics