A note on computing set overlap classes

DOI10.1016/J.IPL.2008.05.005zbMATH Open1193.68283arXiv0711.4573OpenAlexW1986933608MaRDI 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)

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.

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

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

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)

Cites Work

• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

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

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)