๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A More Efficient Approximation Scheme for Tree Alignment

โœ Scribed by Wang, Lusheng; Jiang, Tao; Gusfield, Dan

Book ID
118177506
Publisher
Society for Industrial and Applied Mathematics
Year
2000
Tongue
English
Weight
201 KB
Volume
30
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Improved Approximation Algorithms for Tr
Improved Approximation Algorithms for Tree Alignment
โœ Lusheng Wang; Dan Gusfield ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 251 KB

Multiple sequence alignment is a task at the heart of much of current computaw x tional biology 4 . Several different objective functions have been proposed to formalize the task of multiple sequence alignment, but efficient algorithms are lacking in each case. Thus multiple sequence alignment is on

More Efficient Algorithm for Ordered Tre
More Efficient Algorithm for Ordered Tree Inclusion
โœ Weimin Chen ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 221 KB

Given two ordered trees S S and T T, the tree inclusion problem is to determine whether it is possible to obtain S S from T T by deleting nodes. Recently, this problem has been recognized as an important primitive in query processing for ลฝ< ลฝ .< < <. structured text databases. In this paper we prese

A fully polynomial bicriteria approximat
A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem
โœ Sung-Pil Hong; Sung-Jin Chung; Bum Hwan Park ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 213 KB

We propose a fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. First, an exact pseudo-polynomial algorithm is developed based on a two-variable extension of the well-known matrix-tree theorem. The scaling and approximate binary search techniques are then uti