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 metadatas
Contributor : Simon Vilmin <>
Submitted on : Sunday, June 21, 2020 - 5:00:01 PM
Last modification on : Saturday, July 4, 2020 - 3:36:51 AM


Files produced by the author(s)




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



Record views


Files downloads