Skip to Main content Skip to Navigation

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\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.
Document type :
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Binh-Minh Bui-Xuan Connect in order to contact the contributor
Submitted on : Wednesday, January 30, 2008 - 4:24:45 PM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM
Long-term archiving on: : Tuesday, September 21, 2010 - 3:16:28 PM



  • HAL Id : lirmm-00175766, version 2


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



Record views


Files downloads