1989 Reports
Online Maintenance of Minimal Directed Hypergraphs
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).
Subjects
Files
- cucs-435-89.pdf application/pdf 616 KB Download File
More About This Work
- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-435-89
- Published Here
- December 22, 2011