Dynamic Shortest Path Algorithms for Hypergraphs
Jianhang Gao, Qing Zhao, Wei Zhong Ren, Ananthram Swami, Ram Ramanathan, Amotz Bar-Noy · arXiv (Cornell University) · 2012
A hypergraph is a set V of vertices and a set of non-empty subsets of V, called hyperedges. Unlike graphs, hypergraphs can capture higher-order interactions in social and communication networks that go beyond a simple union of pairwise relationships. In this paper, we consider the shortest path problem in hypergraphs. We develop two algorithms for finding and maintaining the shortest hyperpaths in a dynamic network with both weight and topological changes. These two algorithms are the first to address the fully dynamic shortest path problem in a general hypergraph. They complement each other by partitioning the application space based on the nature of the change dynamics and the type of the hypergraph.