A Representation Theorem for union-difference Families and Application - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

A Representation Theorem for union-difference Families and Application

Résumé

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.
Fichier principal
Vignette du fichier
BH08.pdf (192.33 Ko) Télécharger le fichier
Loading...

Dates et versions

lirmm-00175766 , version 1 (01-10-2007)
lirmm-00175766 , version 2 (30-01-2008)

Identifiants

  • HAL Id : lirmm-00175766 , version 2

Citer

Binh-Minh Bui-Xuan, Michel Habib. A Representation Theorem for union-difference Families and Application. [Research Report] RR-07020, LIRMM. 2007. ⟨lirmm-00175766v2⟩
171 Consultations
262 Téléchargements

Partager

Gmail Facebook X LinkedIn More