Directed hypergraphs: Introduction and fundamental algorithms—A survey
| Autor: | Giorgio Ausiello, Luigi Laura |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
General Computer Science Reachability problem Generalization Transitive closure 0102 computer and information sciences 02 engineering and technology Context-free grammar Propositional calculus 01 natural sciences Transitive reduction Theoretical Computer Science Combinatorics Set (abstract data type) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Boolean satisfiability problem Mathematics |
| Zdroj: | Theoretical Computer Science. 658:293-306 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2016.03.016 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect