arXiv Open Access 2017

Consensus Patterns parameterized by input string length is W[1]-hard

Laurent Bulteau

Lihat Sumber

Abstrak

We consider the Consensus Patterns problem, where, given a set of input strings, one is asked to extract a long-enough pattern which appears (with some errors) in all strings. We prove that this problem is W[1]-hard when parameterized by the maximum length of input strings.

Topik & Kata Kunci

cs.CC

Penulis (1)

Laurent Bulteau

Format Sitasi

APA MLA BibTeX

Bulteau, L. (2017). Consensus Patterns parameterized by input string length is W[1]-hard. https://arxiv.org/abs/1702.08238

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓