String Noninclusion Optimization Problems

DOI10.1137/S0895480192234277MaRDI QIDQ4210217zbMATH OpenOpenAlexFDO

Authors A. R. Rubinov, Vadim G. Timkovsky

Publication date 21 September 1998

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480192234277

zbMATH Keywords

commonlongestNP-hard problempolynomial-time algorithmshorteststring inclusionsubsequencesubstringsupersequencesuperstring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• Finding the longest common nonsuperstring in linear time
• Combined super-/substring and super-/subsequence problems
• Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model
• Maximal common subsequences and minimal common supersequences

Cited in

(10)

• On trace inclusion optimization problems
• A new graph model and algorithms for consistent superstring problems
• Restricted common superstring and restricted common supersequence
• Avoiding substrings in compositons
• scientific article; zbMATH DE number 2170423 (Why is no real title available?)
• Non-Looping String Rewriting
• Consistent subsequences and supersequences
• On the approximation of longest common nonsupersequences and shortest common nonsubsequences
• Shortest consistent superstrings computable in polynomial time
• Finding the longest common nonsuperstring in linear time

This page was built for publication: String Noninclusion Optimization Problems

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