Separating sets of strings by finding matching patterns is almost always hard
From MaRDI portal
Publication:507598
DOI10.1016/j.tcs.2016.12.018zbMath1356.68101arXiv1604.03243OpenAlexW2963448547MaRDI QIDQ507598
Giuseppe Lancia, Luke Mathieson, Pablo Moscato
Publication date: 6 February 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1604.03243
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)
Cites Work
- Fundamentals of parameterized complexity
- Parameterized complexity analysis for the closest string with wildcards problem
- Finding patterns common to a set of strings
- Approximation algorithms for combinatorial problems
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- Approximation algorithms for the class cover problem
- The \(k\)-feature set problem is \(W[2\)-complete]
- Using patterns to form homogeneous teams
- Parameterized intractability of distinguishing substring selection
- Parametrized complexity theory.
- The Parameterized Complexity of k-Edge Induced Subgraphs
- On the closest string and substring problems
- Every Planar Map is Four Colorable
- An analysis of the W*-hierarchy
- Pattern-Guided k-Anonymity
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Separating sets of strings by finding matching patterns is almost always hard