Parameterized intractability of distinguishing substring selection

DOI10.1007/s00224-004-1185-zzbMath1103.68489OpenAlexW2122833316MaRDI QIDQ2432546

Jiong Guo, Jens Gramm, Rolf Niedermeier

Publication date: 25 October 2006

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-004-1185-z

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (5)

On the ordered list subgraph embedding problems ⋮ On approximating string selection problems with outliers ⋮ LP-based heuristics for the distinguishing string and substring selection problems ⋮ Separating sets of strings by finding matching patterns is almost always hard ⋮ An improved lower bound on approximation algorithms for the closest substring problem

This page was built for publication: Parameterized intractability of distinguishing substring selection