# A Representation Theorem for union-difference Families and Application

1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We give a quadratic $O(|X|^2)$ space representation based on a canonical tree for any subset family $F\subseteq2^X$ holding the closure under union and difference of overlapping members. The cardinal of $F$ is potentially in $O(2^{|X|})$, and its size higher. As far as we know this is the first representation theorem for such families. As an application of this framework we obtain a uniqueness decomposition theorem on a digraph decomposition that captures and is strictly more powerful than the well-studied modular decomposition. Moreover a polynomial time decomposition algorithm for this case is described.
Type de document :
Rapport
[Research Report] RR-07020, LIRMM. 2007

Littérature citée [21 références]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00175766
Contributeur : Binh-Minh Bui-Xuan <>
Soumis le : mercredi 30 janvier 2008 - 16:24:45
Dernière modification le : vendredi 4 janvier 2019 - 17:32:56
Document(s) archivé(s) le : mardi 21 septembre 2010 - 15:16:28

### Identifiants

• HAL Id : lirmm-00175766, version 2

### Citation

Binh-Minh Bui-Xuan, Michel Habib. A Representation Theorem for union-difference Families and Application. [Research Report] RR-07020, LIRMM. 2007. 〈lirmm-00175766v2〉

### Métriques

Consultations de la notice

## 187

Téléchargements de fichiers