𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Faster implementation of a shortest superstring approximation

✍ Scribed by Dan Gusfield

Book ID
103103969
Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
373 KB
Volume
51
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Sequential and Parallel Approximation of
Sequential and Parallel Approximation of Shortest Superstrings
✍ Artur Czumaj; Leszek Gąsieniec; Marek Piotrów; Wojciech Rytter 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 316 KB

Superstrings have many applications in data compression and genetics. However, the decision version of the shortest superstring problem is N N P P-complete. In this paper we examine the complexity of approximating shortest superstrings. There are two basic measures of the approximations: the length

A Faster Implementation of a Parallel Tr
A Faster Implementation of a Parallel Tree Contraction Scheme and Its Application on Distance-Hereditary Graphs
✍ Sun-yuan Hsieh; Chin-Wen Ho; Tsan-sheng Hsu; Ming-Tat Ko; Gen-Huey Chen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 261 KB

We consider a parallel tree contraction scheme which in each contraction phase Ž . Ž . removes leaves and nodes in the maximal chains. Let T n and P n denote the time and processor complexity required to compute the all nearest smaller values Ž . ANSV and the minimum of n values for input elements d