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(ℋ)) worst case time under a sequence of L hyperarc weight increments and hyperarc deletions, where C is the maximum weight of minimum hyperpaths in ℋ and size(ℋ) 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. © 2004 Elsevier B.V. All rights reserved.
Partially dynamic maintenance of minimum weight hyperpaths / Ausiello, Giorgio; Franciosa, Paolo Giulio; Daniele, Frigioni. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - STAMPA. - 3:1(2005), pp. 27-46. [10.1016/j.jda.2003.12.005]
Partially dynamic maintenance of minimum weight hyperpaths
AUSIELLO, Giorgio;FRANCIOSA, Paolo Giulio;
2005
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(ℋ)) worst case time under a sequence of L hyperarc weight increments and hyperarc deletions, where C is the maximum weight of minimum hyperpaths in ℋ and size(ℋ) 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. © 2004 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
