Reconstructing Set Partitions

Vladimir Grebinski 1 Gregory Kucherov 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We study the following combinatorial search problem: Reconstruct an unknown partition of the set [n]={1,...,n} into at most K disjoint non-empty subsets (classes) by making queries about subsets $Q_i \subseteq [n]$ such that the query returns the number of classes represented in $Q_i$. The goal is to reconstruct the whole partition with as few queries as possible. We also consider a variant of the problem where a representative of each class should be found without necessarily reconstructing the whole partition. Besides its theoretical interest, the problem has practical applications. Paper \cite{SBAW-RECOMB97} considers a physical mapping method based on hybridizing probes to chromosomes using the FISH technology. Under some reasonable assumptions, the method amounts to finding a partition of probes determined by the chromosome they hybridize to, and actually corresponds to the above formalization.
Type de document :
Communication dans un congrès
Tenth Annual ACM-SIAM Symposium on Discrete Algorithms - SODA'99, 1999, Baltimore, Maryland/US, ACM/SIAM, pp.2, 1999
Liste complète des métadonnées

https://hal.inria.fr/inria-00098744
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:32:28
Dernière modification le : mardi 6 mars 2018 - 17:40:58
Document(s) archivé(s) le : mercredi 29 mars 2017 - 12:41:52

Fichiers

Identifiants

  • HAL Id : inria-00098744, version 1

Collections

Citation

Vladimir Grebinski, Gregory Kucherov. Reconstructing Set Partitions. Tenth Annual ACM-SIAM Symposium on Discrete Algorithms - SODA'99, 1999, Baltimore, Maryland/US, ACM/SIAM, pp.2, 1999. 〈inria-00098744〉

Partager

Métriques

Consultations de la notice

152

Téléchargements de fichiers

59