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.
Type de document :
Rapport
RR-07031, 2007
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00199916
Contributeur : Binh-Minh Bui-Xuan <>
Soumis le : jeudi 20 décembre 2007 - 00:04:01
Dernière modification le : jeudi 11 janvier 2018 - 06:17:42

Identifiants

  • HAL Id : lirmm-00199916, version 1

Collections

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〉

Partager

Métriques

Consultations de la notice

347