HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:32:28 AM
Last modification on : Friday, February 4, 2022 - 3:31:21 AM
Long-term archiving on: : Wednesday, March 29, 2017 - 12:41:52 PM


  • HAL Id : inria-00098744, version 1



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



Record views


Files downloads