• Борис Клемц
  • Тамара Мчедлидзе
  • Мартин Ноленбург

Резюме

В тази статия представяме алгоритъм за O (n 2 (m + log n)) - време за изчисляване на поддръжка на дърво с минимално тегло (ако има такава) на хиперграф H = (V, S) с n върхове и m хипергенери. Това подобрява най-добре познатия досега алгоритъм с време на работа O (n 4 m 2). Опора на H е графика G на V, така че всеки свръхъгълник в S индуцира свързан подграф в G. Ако G е дърво, то се нарича дървесна опора и е минимална опора на дърво, ако неговото тегло на ръба е минимално за зададена функция на тежестта на ръба. Дървесните опори на хиперграфи имат няколко приложения, от анализ на социални мрежи и проблеми с мрежовия дизайн до визуализация на хиперграфи и диаграми на Ойлер. По-специално показваме как подпората на дърво с минимално тегло може да се използва за генериране на пропорционална на площта диаграма на Ойлер, която удовлетворява типичните условия на добре оформена форма и допълнително минимизира броя на едновременните криви на зададените граници в диаграмата на Ойлер.

минимални

Ключови думи

Визуализация

Не може да се покаже визуализация. Изтеглете PDF за визуализация.