A Note on Computing Set Overlap Classes - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Information Processing Letters Year : 2008

A Note on Computing Set Overlap Classes

Abstract

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 and versions

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

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More