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

https://hal.uca.fr/hal-02876740
Contributor : Simon Vilmin <>
Submitted on : Sunday, June 21, 2020 - 5:00:01 PM
Last modification on : Saturday, July 4, 2020 - 3:36:51 AM

File

NourineVilmin-Dihypergraphs.pd...
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

34

Files downloads

33