Online Maintenance of Minimal Directed Hypergraphs

Giuseppe F. Italiano; Umberto Nanni

Online Maintenance of Minimal Directed Hypergraphs
Italiano, Giuseppe F.
Nanni, Umberto
Computer Science
Persistent URL:
Columbia University Computer Science Technical Reports
Part Number:
Department of Computer Science, Columbia University
Publisher Location:
New York
In this paper we deal with directed hypergraphs, a generalization of directed graphs previously introduced in the literature. In particular, we investigate the problem of maintaining efficiently information about minimal hyperpaths while new hyperarcs are inserted. We consider several definitions of minimal hyperpath and we prove that accordingly to some of such definitions the problem of finding the minimal hyperpath is NP-complete, while hyperpaths with minimal GAP and minimal RANK can be found in polynomial time. We deal with this problem in an online fashion, by allowing insertions of hyperarcs in the hypergraphs. We present data structures and algorithms which allow to return a hyperpath with minimal GAP or RANK between an arbitrarily given pair of nodes in a time which is linear in its size. The total time required to maintain the data structure during the insertion of new hyperarcs is (9(m n2) for min-GAP and (9(m n2 log n) for min-RANK (where m is the total size of the description of the hyperarcs and n is the number of nodes). These results are useful in applications where directed hypergraphs are known to be a suitable model (e.g. transition networks, rewriting systems, database schemes, logic programming and problem solving).
Computer science
Item views
text | xml
Suggested Citation:
Giuseppe F. Italiano, Umberto Nanni, , Online Maintenance of Minimal Directed Hypergraphs, Columbia University Academic Commons, .

Columbia University Libraries | Policies | FAQ