A note on computing set overlap classes

DOI10.1016/J.IPL.2008.05.005zbMATH Open1193.68283OpenAlexW1986933608MaRDI QIDQ975443FDOQ975443

Authors Pierre Charbit, Vincent Limouzy, Fabien De Montgolfier, Mathieu Raffinot, Michaël Rao, M. A. Habib

Publication date 9 June 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.4573

zbMATH Keywords

graph algorithmsset systemoverlap class

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Abstract: Let $calV$ be a finite set of $n$ elements and $calF=X_1,X_2,>\mathrm{...},X_m$ a family of $m$ subsets of $calV.$ Two sets $X_i$ and $X_j$ of $calF$ overlap if $X_{i}cap{X}_{j}eqemptyset,$ $X_{j}setminus{X}_{i}eqemptyset,$ and $X_{i}setminus{X}_{j}eqemptyset.$ Two sets $X,YincalF$ are in the same overlap class if there is a series $X=X_1,X_2,\mathrm{...},X_k=Y$ of sets of $calF$ in which each $X_i{X}_{i+1}$ overlaps. In this note, we focus on efficiently identifying all overlap classes in $O(n+su{m}_{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.

Recommendations

• A class of Cantor sets with overlaps
• A bound on the overlap of same-sized subsets
• BIPARTITIONING INTO OVERLAPPING SETS
• scientific article; zbMATH DE number 6157240
• Classes of sets with large intersection
• Overlap function-based amongness spaces
• scientific article; zbMATH DE number 3955290
• An overlapping theorem with applications

Cites work

• scientific article; zbMATH DE number 1775413 (Why is no real title available?)
• A certifying algorithm for the consecutive-ones property
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition

Cited in

(5)

• A bound on the overlap of same-sized subsets
• A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs
• Systems of overlap representation for families of intervals
• Consecutive ones property testing: cut or swap
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs

This page was built for publication: A note on computing set overlap classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q975443)