Directed hypergraphs: Introduction and fundamental algorithms—A survey
详细信息 查看全文
- 作者：Giorgio Ausiello ausiello@dis.uniroma1.it ; Luigi Laura ; laura@dis.uniroma1.it ;
- 关键词：Directed hypergraphs ; Transitive closure ; Transitive reduction ; Shortest hyperpaths
- 刊名：Theoretical Computer Science
- 出版年：2017
- 出版时间：7 January 2017
- 年：2017
- 卷：658
- 期：part_PB
- 页码：293-306
- 全文大小：603 K
- 卷排序：658
文摘
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,v>, S non empty subset of V and v∈Vv∈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.