The generalized definitions of the two-dimensional largest common substructure problems

DOI10.1007/s00453-020-00685-8zbMath1442.68155OpenAlexW3006330111MaRDI QIDQ2182100

Chang-Biau Yang, Yung-Hsing Peng, Hsuan-Tsung Chiu, Huang-Ting Chan

Publication date: 21 May 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00685-8

zbMATH Keywords

satisfiabilityNP-hardnessAPX-hardnesslongest common subsequence2D string3-dimensional matching

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32) Computational aspects of satisfiability (68R07)

Related Items (1)

An efficient algorithm for the longest common palindromic subsequence problem

Uses Software

• TED
• RTED

Cites Work

• Unnamed Item
• Unnamed Item
• Computational complexity of similarity retrieval in a pictorial database
• Completeness in approximation classes
• Dynamic programming algorithms for the mosaic longest common subsequence problem
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Algorithms for computing variants of the longest common subsequence problem
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Optimization, approximation, and complexity classes
• A short note on the approximability of the maximum leaves spanning tree problem
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Generalized LCS
• Efficient algorithms for finding interleaving relationship between sequences
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• A linear space algorithm for computing maximal common subsequences
• A fast algorithm for computing longest common subsequences
• Fast Pattern Matching in Strings
• Introduction to the theory of complexity and approximation algorithms
• Reducibility among Combinatorial Problems
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

This page was built for publication: The generalized definitions of the two-dimensional largest common substructure problems