A Representation Theorem for Union-Difference Families and Application - Laboratoire d'Informatique Algorithmique, Fondements et Applications Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

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\subseteq 2^X closed under the union and the difference of its overlapping members. The cardinality of F is potentially in O(2^|^X|), and the total cardinality of its members even higher. As far as we know this is the first representation result for such families. As an application of this framework we obtain a unique digraph decomposition that not only captures, but also is strictly more powerful than the well-studied modular decomposition. A polynomial time decomposition algorithm for this case is described.
Fichier principal
Vignette du fichier
BH08.pdf (346.96 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00324969 , version 1 (16-09-2019)

Identifiants

Citer

Binh-Minh Bui-Xuan, Michel Habib. A Representation Theorem for Union-Difference Families and Application. LATIN: Latin American Symposium, Apr 2008, Búzios, Brazil. pp.492-503, ⟨10.1007/978-3-540-78773-0_43⟩. ⟨lirmm-00324969⟩
225 Consultations
89 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More