Skip to Main content Skip to Navigation
Reports

A Representation Theorem for union-difference Families and Application

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 :
Reports
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00175766
Contributor : Binh-Minh Bui-Xuan Connect in order to contact the contributor
Submitted on : Monday, October 1, 2007 - 11:03:25 AM
Last modification on : Monday, October 11, 2021 - 1:22:09 PM
Long-term archiving on: : Friday, April 9, 2010 - 4:51:00 PM

File

Identifiers

  • HAL Id : lirmm-00175766, version 1

Collections

Citation

Binh-Minh Bui-Xuan, Michel Habib. A Representation Theorem for union-difference Families and Application. RR-07020, 2007. ⟨lirmm-00175766v1⟩

Share

Metrics

Record views

9

Files downloads

35