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.
Domaines
Mathématique discrète [cs.DM]
Loading...