Skip to Main content Skip to Navigation
Reports

Representing Partitive Crossing Families and Union-Difference Families, with Application to Sesquimodular Decomposition

Abstract : A subset family $\cf\subseteq2^X$ is partitive crossing if it is close under the union, the intersection, and the difference of its crossing members; it is a union-difference family if closed under the union and the difference of its overlapping members. In both cases, the cardinality of $\cf$ is potentially in $O(2^{|X|})$, and the total cardinality of its members even higher. We give a linear $O(|X|)$ and a quadratic $O(|X|^2)$ space representation based on a canonical tree for any partitive crossing family and union-difference family, respectively. As an application of this framework we obtain a unique digraph decomposition and a unique decomposition of $2-$structure. Both of them not only captures, but also is strictly more powerful than the well-studied modular decomposition and clan decomposition. Polynomial time decomposition algorithms for both cases are described.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00199916
Contributor : Binh-Minh Bui-Xuan <>
Submitted on : Thursday, December 20, 2007 - 12:04:01 AM
Last modification on : Saturday, March 28, 2020 - 2:14:37 AM

Identifiers

  • HAL Id : lirmm-00199916, version 1

Citation

Binh-Minh Bui-Xuan, Michel Habib, Michaël Rao. Representing Partitive Crossing Families and Union-Difference Families, with Application to Sesquimodular Decomposition. RR-07031, 2007. ⟨lirmm-00199916⟩

Share

Metrics

Record views

645