Linear approximation of shortest superstrings
From MaRDI portal
Publication:4310837
DOI10.1145/179812.179818zbMath0812.68075OpenAlexW2134761228WikidataQ129735146 ScholiaQ129735146MaRDI QIDQ4310837
Mihalis Yannakakis, Tao Jiang, John Tromp, Avrim L. Blum, Ming Li
Publication date: 3 November 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/1422
Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Algorithms on strings (68W32)
Related Items
An external-memory algorithm for string graph construction, Faster implementation of a shortest superstring approximation, Optimal solutions in the multi-location inventory system with transshipments, The greedy algorithm for shortest superstrings, Improved length bounds for the shortest superstring problem, All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent, Inferring a tree from walks, A Probabilistic PTAS for Shortest Common Superstring, Combinatorial algorithms for DNA sequence assembly, Physical mapping of chromosomes: A combinatorial problem in molecular biology, Combined super-/substring and super-/subsequence problems, On the approximability of the maximum common subgraph problem, A probabilistic PTAS for shortest common superstring, Recognition of overlap graphs, Unnamed Item, Why Greed Works for Shortest Common Superstring Problem, Minimum-Weight Cycle Covers and Their Approximability, On the greedy algorithm for the shortest common superstring problem with reversals, On the Shortest Common Superstring of NGS Reads, On the approximation of shortest common supersequences and longest common subsequences, Collapsing Superstring Conjecture, Restricted and swap common superstring: a multivariate algorithmic perspective, From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization, Restricted Common Superstring and Restricted Common Supersequence, CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM, Relationship between superstring and compression measures: new insights on the greedy conjecture, Hierarchical overlap graph, Sharpening Occam's razor, Fast prefix matching of bounded strings, Minimum-weight cycle covers and their approximability, A \(2_3^2\) superstring approximation algorithm, Why greed works for shortest common superstring problem, The approximability of the weighted Hamiltonian path completion problem on a tree, A combinatorial approach to the design of vaccines, A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem, Practical lower and upper bounds for the Shortest Linear Superstring, Superstrings with multiplicities, Diagram processing: Computing with diagrams
