✦ LIBER ✦

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

✍ Scribed by Tatsuya Akutsu; Magnús M. Halldórsson

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 136 KB
Volume: 233
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(97)00278-8

No coin nor oath required. For personal study only.

✦ Synopsis

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 search algorithm which approximates both problems within a factor of O(n= log n) is presented. For trees of bounded degree, an improved algorithm which approximates the largest common subtree within a factor of O(n= log 2 n) is presented. Moreover, several variants of the largest common subtree problem are studied.

📜 SIMILAR VOLUMES

Algorithm for finding one of the largest

Algorithm for finding one of the largest common subgraphs of two three-dimensional graph structures

✍ Sumio Masuda; Hiroyuki Yoshioka; Eiichi Tanaka 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB 👁 1 views

Given two connected graphs G a = (V a , E a ) and G b = (V b , E b ) with three-dimensional structures. Let n a = |V a |, m a = |E a |, n b = |V b |, and m b = |E b |. Let the maxi- mum order of a vertex in G a (G b ) be l a (l b ). Initially this paper offers a method to find a largest common subgr

Finding the common point of a system of

Finding the common point of a system of convex sets and solving mathematical-programming optimization problems by the orthogonal descent method

✍ M. B. Shchepakin 📂 Article 📅 1993 🏛 Springer US 🌐 English ⚖ 441 KB

The relaxation method of finding the com

The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming

✍ L.M. Bregman 📂 Article 📅 1967 🏛 Elsevier Science ⚖ 824 KB

Some remarks on the set of common fixed

Some remarks on the set of common fixed points of one-parameter semigroups of nonexpansive mappings in Banach spaces with the Opial property

✍ Tomonari Suzuki 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 247 KB

The effect of potassium gibberellate and

The effect of potassium gibberellate and naphtaline acetamide on pod setting in intervarietal crosses of common bean,Phaseolus vulgarisL.

✍ A. Sarafi; B. Yazdi-Samadi 📂 Article 📅 1973 🏛 Springer 🌐 English ⚖ 142 KB

The potential effects of two hormones, namely potassium gibberellate (P .G.) and naphtaline acetamide (N .A .), on pod setting in bean were investigated in three crossing programs, set up with five varieties of bean . Shortly after each crossing, a cut was made on the calyx and a mixture of lanoline

BRE profiles Europe's setting of common

BRE profiles Europe's setting of common concrete standards: Copies of ‘European concreting practice: a summary’ and of the individual Information Papers on Germany, Sweden, Italy and France are available from the BRE Bookshop, Building Research Establishment, Garston, Watford WD2 7JR, price £3.50 each (plus 35p p&p)

📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 122 KB