Minimal discriminating words problem revisited

Paweł Gawrychowski, Gregory Kucherov, Yakov Nekrich, Tatiana Starikovskaya

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)

Abstract

We revisit two variants of the problem of computing minimal discriminating words studied in [5]. Given a pattern P and a threshold d, we want to report (i) all shortest extensions of P which occur in less than d documents, and (ii) all shortest extensions of P which occur only in d selected documents. For the first problem, we give an optimal solution with constant time per output word. For the second problem, we propose an algorithm with running time O(|P| + d · (1 + output)) improving the solution of [5].

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings
PublisherSpringer Verlag
Pages129-140
Number of pages12
ISBN (Print)9783319024318
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event20th International Symposium on String Processing and Information Retrieval, SPIRE 2013 - Jerusalem, Israel
Duration: 7 Oct 20139 Oct 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8214 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Symposium on String Processing and Information Retrieval, SPIRE 2013
Country/TerritoryIsrael
CityJerusalem
Period7/10/139/10/13

Fingerprint

Dive into the research topics of 'Minimal discriminating words problem revisited'. Together they form a unique fingerprint.

Cite this