Reconstructing set partitions

Vladimir Grebinski, Gregory Kucherov

Research output: Contribution to conferencePaperpeer-review

2 Citations (Scopus)

Abstract

A study was conducted to solve the given combinatorial search problem of reconstructing an unknown partition of the set [n] = {1, ..., n} into at most K disjoint non-empty subsets by making queries about subsets Qi ⊂ or = [n] such that the query returns the number of classes represented in Qi. The goal is to reconstruct the whole partition with as few queries as possible. A variant of the problem where a representative of each class should be found without necessarily reconstructing the whole partition was also considered.

Original languageEnglish
PagesS915-S916
Publication statusPublished - 1999
Externally publishedYes
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: 17 Jan 199919 Jan 1999

Conference

ConferenceProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period17/01/9919/01/99

Fingerprint

Dive into the research topics of 'Reconstructing set partitions'. Together they form a unique fingerprint.

Cite this