✦ LIBER ✦

On the approximation of longest common nonsupersequences and shortest common nonsubsequences

✍ Scribed by Louxin Zhang

Book ID: 107948804
Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 639 KB
Volume: 143
Category: Article
ISSN: 0304-3975
DOI: 10.1016/0304-3975(94)00257-j

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the parameterized complexity of the f

On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems

✍ Krzysztof Pietrzak 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 205 KB

We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W ½1-hard. Unless W ½1 ¼ FPT; this rules out the existence of algorithms with time complexity of Oð f ðkÞn a Þ for those pro

On the approximation of largest common s

On the approximation of largest common subtrees and largest common point sets

✍ Tatsuya Akutsu; Magnús M. Halldórsson 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 136 KB

This paper considers the approximability of the largest common subtree and the largest common point-set problems, which have applications in molecular biology. It is shown that the problems cannot be approximated within a factor of n 1-in polynomial time for any ¿0 unless NP ⊆ ZPP, while a general s

Bounding the Expected Length of Longest

Bounding the Expected Length of Longest Common Subsequences and Forests

✍ R. A. Baeza-Yates; R. Gavaldà; G. Navarro; R. Scheihing 📂 Article 📅 1999 🏛 Springer 🌐 English ⚖ 242 KB

On the complexity of finding common appr

On the complexity of finding common approximate substrings

✍ Patricia A. Evans; Andrew D. Smith; H.Todd Wareham 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 323 KB

Problems associated with ÿnding strings that are within a speciÿed Hamming distance of a given set of strings occur in several disciplines. In this paper, we use techniques from parameterized complexity to assess non-polynomial time algorithmic options and complexity for the COMMON APPROXIMATE SUBST

Numerical comparison of the isotropic-co

Numerical comparison of the isotropic-common-ray and anisotropic-common-ray approximations of the coupling ray theory

✍ Petr Bulant; Luděk Klimeš 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 1003 KB

On the Logic of Common Belief

✍ Giacomo Bonanno 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 367 KB

We investigate an axiomatization of the notion of common belief (knowledge) that makes use of no rules of inference (apart from Modus Ponens and Necessitation) and highlight the property of the set of accessibility relations that characterizes each axiom.