NP-completeness of special string editing problems

DOI10.4213/MVK103zbMATH Open1472.68063OpenAlexW2789416646MaRDI QIDQ4959092FDOQ4959092

Authors: S. S. Martynov 

Publication date: 15 September 2021

Published in: Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/mvk103

Recommendations

• scientific article; zbMATH DE number 8125
• Edit distance with block deletions
• scientific article; zbMATH DE number 3883626
• The shortest common nonsubsequence problem is NP-complete
• Topology of strings: median string is NP-complete

zbMATH Keywords

NP-complete problemsblock codestring editing problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• A Probabilistic Analysis of a String Editing Problem and its Variations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constrained many-to-one string editing with memory

This page was built for publication: NP-completeness of special string editing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4959092)