Problém minimálního společného dělení řetězců: obtížnost a aproximace

Abstrakt

V tomto článku studujeme problém minimálního společného dělení dvou řetězců. Dokážeme, že již velice omezená varianta problému je NP-těžká a APX-těžká, a také přinášíme několik aproximačních algoritmů.

Klíčová slova

• Minimum
• Common
• String
• Partition
• Problem
• Hardness
• Approximations