An algorithm of finding an acyclic f -graph for a family of sets

Abstract

Acyclic families of sets are investigated. A theorem giving necessary and sufficient conditions for the family of sets to be acyclic is formulated and proved. Then an algorithm is described of finding the acyclic f-graph for a given family of sets whenever this family is acyclic. Its computational complexity is equal to $\mathcal{O}\mathrm{(}{\mathit{n}}^3+{\mathit{n}}^2\mathit{k}\mathrm{)}$ , so it is better than the other algorithms known so far.