A Note on Computing Set Overlap Classes - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Information Processing Letters Année : 2008

A Note on Computing Set Overlap Classes

Résumé

Let ${\cal V}$ be a finite set of $n$ elements and ${\cal F}=\{X_1,X_2, \ldots , X_m\}$ a family of $m$ subsets of ${\cal V}.$ Two sets $X_i$ and $X_j$ of ${\cal F}$ overlap if $X_i \cap X_j \neq \emptyset,$ $X_j \setminus X_i \neq \emptyset,$ and $X_i \setminus X_j \neq \emptyset.$ Two sets $X,Y\in {\cal F}$ are in the same overlap class if there is a series $X=X_1,X_2, \ldots, X_k=Y$ of sets of ${\cal F}$ in which each $X_iX_{i+1}$ overlaps. In this note, we focus on efficiently identifying all overlap classes in $O(n+\sum_{i=1}^m |X_i|)$ time. We thus revisit the clever algorithm of Dahlhaus of which we give a clear presentation and that we simplify to make it practical and implementable in its real worst case complexity. An useful variant of Dahlhaus's approach is also explained.

Dates et versions

lirmm-00325371 , version 1 (29-09-2008)

Identifiants

Citer

Pierre Charbit, Michel Habib, Vincent Limouzy, Fabien de Montgolfier, Mathieu Raffinot, et al.. A Note on Computing Set Overlap Classes. Information Processing Letters, 2008, 108 (4), pp.186-191. ⟨10.1016/j.ipl.2008.05.005⟩. ⟨lirmm-00325371⟩
167 Consultations
0 Téléchargements

Altmetric

Partager

More