×
Maier, David; Ullman, Jeffrey D.

Connections in acyclic hypergraphs. (English) Zbl 0557.05054

Theor. Comput. Sci. 32, 185-199 (1984).
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 M. H. Graham, On the universal relation, Tech. Rept., Univ. of Toronto (1979)] and the process of tableau reduction [see A. V. Aho, Y. Sagiv and J. D. Ullman, SIAM J. Comput. 8, 218-246 (1979; Zbl 0412.68041)] is also exhibited.
Reviewer: L.Zaremba

Cited in 16 Documents

MSC:

05C65 Hypergraphs
05C40 Connectivity

Keywords:

biconnected components; independent path; Graham reduction; acyclic hypergraphs; tableau reduction

Citations:

Zbl 0412.68041
PDFBibTeX XMLCite
\textit{D. Maier} and \textit{J. D. Ullman}, Theor. Comput. Sci. 32, 185--199 (1984; Zbl 0557.05054)
Full Text: DOI

References:

[1] Aho, A. V.; Sagiv, Y.; Ullman, J. D., Equivalence of relational expressions, SIAM J. Comput., 8, 2, 218-246 (1979) · Zbl 0412.68041
[2] Aho, A. V.; Sethi, R.; Ullman, J. D.; Rustin, R., Code optimization and finite Church-Rosser systems, Design and Optimization of Compilers (1972), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[3] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[4] C. Beeri, R. Fagin, D. Maier and M. Yannakakis, On the desirable properties of acyclic database schemes, RJ3131, IBM, San Jose, CA.; C. Beeri, R. Fagin, D. Maier and M. Yannakakis, On the desirable properties of acyclic database schemes, RJ3131, IBM, San Jose, CA. · Zbl 0624.68087
[5] Bernstein, P. A.; Goodman, N., The power of natural semijoins, SIAM J. Comput., 10, 4, 751-771 (1981) · Zbl 0469.68090
[6] Fagin, R.; Mendelzon, A. O.; Ullman, J. D., A simplified universal relation assumption and its properties, ACM TODS, 7, 3, 343-360 (1982) · Zbl 0488.68069
[7] Graham, M. H., On the universal relation (1979), Univ. of Toronto, Tech. Rept.
[8] Maier, D.; Ullman, J. D., Maximal objects and the semantics of universal relation databases, ACM TODS, 8, 1, 1-14 (1983) · Zbl 0536.68081
[9] Yu, C. T.; Ozsoyoglu, M. Z., An algorithm for tree-query membership of a distributed query, Proc. COMPSAAC-79, 306-342 (1979)
[10] Zaniolo, C., Analysis and design of relational schemata for database systems, (Ph.D. Thesis (1976), UCLA)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.