A Representation Theorem for Union-Difference Families and Application

Binh-Minh Bui-Xuan 1 Michel Habib 2
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\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.
Type de document :
Communication dans un congrès
Eduardo Sany Laber and Claudson Bornstein and Loana Tito Nogueira and Luerbio Faria. LATIN'08: 8th Latin American Symposium, Apr 2008, Búzios, Brazil. Springer Berlin / Heidelberg, pp.492-503, 2008, LNCS. 〈http://www.latin08.org〉. 〈10.1007/978-3-540-78773-0_43〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324969
Contributeur : Binh-Minh Bui-Xuan <>
Soumis le : jeudi 25 septembre 2008 - 17:45:02
Dernière modification le : jeudi 15 novembre 2018 - 20:26:55

Identifiants

Collections

Citation

Binh-Minh Bui-Xuan, Michel Habib. A Representation Theorem for Union-Difference Families and Application. Eduardo Sany Laber and Claudson Bornstein and Loana Tito Nogueira and Luerbio Faria. LATIN'08: 8th Latin American Symposium, Apr 2008, Búzios, Brazil. Springer Berlin / Heidelberg, pp.492-503, 2008, LNCS. 〈http://www.latin08.org〉. 〈10.1007/978-3-540-78773-0_43〉. 〈lirmm-00324969〉

Partager

Métriques

Consultations de la notice

171