Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Hierarchical decompositions of dihypergraphs

Abstract : In this paper we are interested in decomposing a dihypergraph H = (V, E) into simpler dihypergraphs, that can be handled more e ciently. We study the properties of dihypergraphs that can be hierarchically decomposed into trivial dihypergraphs, i.e., vertex hypergraph. The hierarchical decomposition is represented by a full labelled binary trees called H-tree, in the fashion of hierarchical clustering. We present a polynomial time and space algorithm to achieve such a decomposition by producing its corresponding H-tree. However , there are dihypergraphs that cannot be completely decomposed into trivial components. Therefore, we relax this requirement to more indecomposable di-hypergraphs called H-factors, and discuss applications of this decomposition to closure systems and lattices.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Simon Vilmin <>
Submitted on : Sunday, June 21, 2020 - 5:00:01 PM
Last modification on : Monday, March 22, 2021 - 10:14:02 AM


Files produced by the author(s)




Lhouari Nourine, Simon Vilmin. Hierarchical decompositions of dihypergraphs. 2020. ⟨hal-02876740⟩



Record views


Files downloads