Representing Partitive Crossing Families and Union-Difference Families, with Application to Sesquimodular Decomposition - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Reports Year : 2007

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.
No file

Dates and versions

lirmm-00199916 , version 1 (20-12-2007)

Identifiers

  • HAL Id : lirmm-00199916 , version 1

Cite

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⟩
372 View
0 Download

Share

More