ALCOMFT-TR-02-11

Giorgio Ausiello, Paolo G. Franciosa and Daniele Frigioni
Partially Dynamic Maintenance of Minimum Weight Hyperpaths
Rome. Work package 4. April 2002.

Abstract: We address the problem of dynamically maintaining minimum weight hyperpaths in a directed hypergraph in a decremental setting. For such 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(max(n,C)·\textrmsize( H)) worst case time under a sequence of hyperarc weight increments and hyperarc deletions, where C is the maximum weight of minimum hyperpaths in H and \textrmsize( 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.

Postscript file: ALCOMFT-TR-02-11.ps.gz (134 kb).