Connections in acyclic hypergraphs (Q762180)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3887742
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Connections in acyclic hypergraphs |
scientific article; zbMATH DE number 3887742 |
Statements
Connections in acyclic hypergraphs (English)
0 references
1984
0 references
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.
0 references
biconnected components
0 references
independent path
0 references
Graham reduction
0 references
acyclic hypergraphs
0 references
tableau reduction
0 references
0.8380266427993774
0 references
0.8099085688591003
0 references
0.7853957414627075
0 references
0.7842045426368713
0 references
0.7819902300834656
0 references
