Back to Search
Start Over
Directed hypergraphs: Introduction and fundamental algorithms—A survey.
- Source :
-
Theoretical Computer Science . Jan2017 Part B, Vol. 658, p293-306. 14p. - Publication Year :
- 2017
-
Abstract
- Just as ordinary hypergraphs are a generalization of graphs, directed hypergraphs (DH) are a natural generalization of digraphs. A DH consists of a set of vertices V and a set of hyperarcs H , where a hyperarc is a pair < S , v > , S non empty subset of V and v ∈ V . DHs have a variety of applications: they have been used to represent functional dependency in databases, Horn formulae in propositional logic, and–or graphs, context free grammars etc. In the paper, after providing a brief historical introduction on the notion of DH and some relevant applications, various problems regarding DHs are surveyed and analyzed. In particular we consider the complexity of the reachability problem (together with its application in the related satisfiability problem for Horn CNF formulae) and the computation of transitive closure and transitive reduction of directed hypergraphs (together with its application to the computation of minimum coverings for a set of functional dependencies). Finally a short introduction to the problem of computing shortest hyperpaths in directed hypergraphs is provided. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH theory
*GEOMETRY
*HYPERGRAPHS
*ALGORITHMS
*MATHEMATICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 658
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 120143164
- Full Text :
- https://doi.org/10.1016/j.tcs.2016.03.016