Home

Online Maintenance of Minimal Directed Hypergraphs

Giuseppe F. Italiano; Umberto Nanni

Title:
Online Maintenance of Minimal Directed Hypergraphs
Author(s):
Italiano, Giuseppe F.
Nanni, Umberto
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-435-89
Publisher:
Department of Computer Science, Columbia University
Publisher Location:
New York
Abstract:
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).
Subject(s):
Computer science
Item views:
346
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use