Publication Details
Title: Optimal Traversal of Directed Hypergraphs
Author: G. Ausiello, G. F. Italiano, and U. Nanni
Group: ICSI Technical Reports
Date: September 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-073.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-073
Bibliographic Reference:
G. Ausiello, G. F. Italiano, and U. Nanni. Optimal Traversal of Directed Hypergraphs. ICSI Technical Report TR-92-073, September 1992
Author: G. Ausiello, G. F. Italiano, and U. Nanni
Group: ICSI Technical Reports
Date: September 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-073.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-073
Bibliographic Reference:
G. Ausiello, G. F. Italiano, and U. Nanni. Optimal Traversal of Directed Hypergraphs. ICSI Technical Report TR-92-073, September 1992