The property of equivalence between subgraphs without articulation points and biconnected components known in ordinary graph theory is generalized to hypergraph theory. The notion of a cyclicity in hypergraphs is understood in a nonstandard way and it is proved that a hypergraph H is acyclic if and only if for no pair of subsets \(N\subset H\), \(M\subset H\), there is an independent path. A relationship between the process of Graham reduction of acyclic hypergraphs [see \textit{M. H. Graham}, On the universal relation, Tech. Rept., Univ. of Toronto (1979)] and the process of tableau reduction [see \textit{A. V. Aho, Y. Sagiv} and \textit{J. D. Ullman}, SIAM J. Comput. 8, 218-246 (1979; Zbl 0412.68041)] is also exhibited.
- A simplied universal relation assumption and its properties
- Equivalences among Relational Expressions
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- Maximal objects and the semantics of universal relation databases
- On the Desirability of Acyclic Database Schemes
- Power of Natural Semijoins
- Canonical and monophonic convexities in hypergraphs
- NP-complete problems simplified on tree schemas
- The tree projection theorem and relational query processing
- Interaction-free multivalued dependency sets
- On hypergraph acyclicity and graph chordality
- A fast algorithm for query optimization in universal-relation databases
- Partially dynamic maintenance of minimum weight hyperpaths
- Decomposable convexities in graphs and hypergraphs
- On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
- Acyclic, connected and tree sets
- An invariant for hypergraphs
- scientific article; zbMATH DE number 5818908 (Why is no real title available?)
- scientific article; zbMATH DE number 5534553 (Why is no real title available?)
- Equivalence between hypergraph convexities
- The sum-product algorithm: algebraic independence and computational aspects
- Fundamentals of Computation Theory
- Chordality properties on graphs and minimal conceptual connections in semantic data models
- On the cut-vertex and the interval transit functions of hypergraphs
- Acyclic join dependency and data base projections
- GYO reductions, canonical connections, tree and cyclic schemas, and tree projections
- A universal table model for categorical databases
This page was built for publication: Connections in acyclic hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q762180)
