arXiv Open Access 2008

Common Permutation Problem

Marián Dvorský

Lihat Sumber

Abstrak

In this paper we show that the following problem is NP-complete: Given an alphabet $Σ$ and two strings over $Σ$, the question is whether there exists a permutation of $Σ$ which is a subsequence of both of the given strings.

Topik & Kata Kunci

cs.CC

Penulis (1)

Marián Dvorský

Format Sitasi

APA MLA BibTeX

Dvorský, M. (2008). Common Permutation Problem. https://arxiv.org/abs/0803.4261

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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