Partially dynamic maintenance of minimum weight hyperpaths (Q1775013)

Minimum weight hyperpaths in directed hypergraphs generalise shortest paths in digraphs and appear in applications such as context-free grammars, relational databases or conjunctions of Horn-clauses, see e.g.\ \textit{G. Ramalingam} and \textit{T. Reps} [J.\ Algorithms 21, 267--305 (1996; Zbl 0861.68035)]. There is an algorithm updating a system of minimum weight hyperpaths in time \(O(L \cdot C + \max\{n,C\} \cdot s)\), where \(L\) is the number of weight increments or hyperarc deletions, \(C\) is the maximum weight of a minimum hyperpath, \(n\) is the number of nodes and \(s\) the size of the hypergraph, if the weight measure is a strict weakly superior function with positive integer values.