Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333107 | Journal of Discrete Algorithms | 2005 | 20 Pages |
Abstract
We address the problem of dynamically maintaining minimum weight hyperpaths in a directed hypergraph in a decremental setting. For such a problem, we provide a new efficient algorithm that works for a wide class of hyperpath weight measures. This algorithm explicitly updates minimum weight hyperpaths in O(L·C+max{n,C}·size(H)) worst case time under a sequence of L hyperarc weight increments and hyperarc deletions, where C is the maximum weight of minimum hyperpaths in H and size(H) is the size of the representation of the hypergraph. Hyperpath weight measures are only required to belong to the class of strict weakly superior functions.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Giorgio Ausiello, Paolo Giulio Franciosa, Daniele Frigioni,