ALCOMFT-TR-02-5

Giorgio Ausiello, Paolo G. Franciosa and Daniele Frigioni
Directed Hypergraphs: Problems, Algorithmic Results, and a Novel Decremental Approach
Rome. Work package 4. March 2002.

Abstract: The purpose of this paper is twofold. First, we review several basic combinatorial problems that have been stated in terms of directed hypergraphs and have been studied in the literature in the framework of different application domains. Among them, transitive closure, transitive reduction, flow and cut problems, and minimum weight traversal problems. For such problems we illustrate some of the most important algorithmic results in the context of both static and dynamic applications. Second, we address a specific dynamic problem which finds several interesting applications, especially in the framework of knowledge representation: the maintenance of minimum weight hyperpaths under hyperarc weight increases and hyperarc deletions. For such problem we provide a new efficient algorithm applicable for a wide class of hyperpath weight measures.

Postscript file: ALCOMFT-TR-02-5.ps.gz (113 kb).