Optimal Traversal of Directed Hypergraphs

TitleOptimal Traversal of Directed Hypergraphs
Publication TypeTechnical Report
Year of Publication1992
AuthorsAusiello, G., Italiano G. F., & Nanni U.
Other Numbers778

A "directed hypergraph" is defined by a set of nodes and a set of "hyperarcs," each of which connects a set of "source" nodes to a single "target" node. Directed hypergraphs are used in several contexts to model different combinatorial structures, such as functional dependencies [20], Horn clauses in propositional calculus [6], AND-OR graphs [17], Petri nets [18]. A "hyperpath," similarly to the analogous notion of path in directed graphs, consists of a connection among nodes using hyperarcs. Unlike paths in graphs, hyperpaths are suitable of different definitions of measure, corresponding to different concepts arising in various applications.In this paper we consider the problem of finding optimal hyperpaths according to several optimization criteria. We show that some of these problems are NP-hard but, if the measure function on hyperpaths matches certain conditions (namely if it is "value-based"), the problem turns out to be tractable. We describe efficient algorithms and data structures to find optimal hyperpaths which can be used with any value-based measure function, since it appears in parametric form. The achieved time bound is O(|H| + n log n) for a hypergraph with n nodes and an overall description of size |H|. Dynamic maintenance of optimal hyperpaths is also considered, and the proposed solution supports insertions of hyperarcs.

Bibliographic Notes

ICSI Technical Report TR-92-073

Abbreviated Authors

G. Ausiello, G. F. Italiano, and U. Nanni

ICSI Publication Type

Technical Report