On finding minimal length superstrings
From MaRDI portal
Publication:1140992
DOI10.1016/0022-0000(80)90004-5zbMath0436.68043OpenAlexW2036145579MaRDI QIDQ1140992
John Gallant, James A. Storer, David Maier
Publication date: 1980
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(80)90004-5
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99)
Related Items (60)
DNA sequencing and string learning ⋮ Approximating shortest superstrings with constraints ⋮ A linear time algorithm for shortest cyclic cover of strings ⋮ Parallel and sequential approximation of shortest superstrings ⋮ The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings ⋮ Improved length bounds for the shortest superstring problem ⋮ A survey on combinatorial optimization in dynamic environments ⋮ All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent ⋮ Inferring a tree from walks ⋮ Combinatorial algorithms for DNA sequence assembly ⋮ Novel evolutionary models and applications to sequence alignment problems ⋮ Combined super-/substring and super-/subsequence problems ⋮ Shortest common superstrings and scheduling with coordinated starting times ⋮ Parameterized complexity of superstring problems ⋮ Non-uniqueness of minimal superpermutations ⋮ Computing Minimum Length Representations of Sets of Words of Uniform Length ⋮ A probabilistic PTAS for shortest common superstring ⋮ Recognition of overlap graphs ⋮ Unnamed Item ⋮ Why Greed Works for Shortest Common Superstring Problem ⋮ Complexity of DNA sequencing by hybridization. ⋮ On the greedy algorithm for the shortest common superstring problem with reversals ⋮ Conjunctive query containment over trees using schema information ⋮ Reoptimization of the shortest common superstring problem ⋮ A linear-time algorithm for finding approximate shortest common superstrings ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ On the Shortest Common Superstring of NGS Reads ⋮ Collapsing Superstring Conjecture ⋮ Modified classical graph algorithms for the DNA fragment assembly problem ⋮ Greedy Shortest Common Superstring Approximation in Compact Space ⋮ Shortest consistent superstrings computable in polynomial time ⋮ NC algorithms for finding a maximal set of paths with application to compressing strings ⋮ A large neighborhood search heuristic for the longest common subsequence problem ⋮ Relationship between superstring and compression measures: new insights on the greedy conjecture ⋮ On the complexity of learning strings and sequences ⋮ Conjunctive query containment over trees ⋮ A note on shortest superstrings with flipping ⋮ Approximating Shortest Superstring Problem Using de Bruijn Graphs ⋮ Computational complexity of isothermic DNA sequencing by hybridization ⋮ Tabu search algorithm for DNA sequencing by hybridization with isothermic libraries ⋮ Sequencing by hybridization with isothermic oligonucleotide libraries ⋮ Sequencing by hybridization with errors: handling longer sequences ⋮ Unnamed Item ⋮ Approximating shortest superstrings with constraints ⋮ Reoptimization of the Shortest Common Superstring Problem ⋮ Settlement fund circulation problem ⋮ Superstring Graph: A New Approach for Genome Assembly ⋮ Approximation algorithms for the shortest common superstring problem ⋮ Inferring a tree from walks ⋮ A \(2_3^2\) superstring approximation algorithm ⋮ Why greed works for shortest common superstring problem ⋮ Computing a longest common subsequence for a set of strings ⋮ A tissue \(P\) system and a DNA microfluidic device for solving the shortest common superstring problem ⋮ A combinatorial approach to the design of vaccines ⋮ A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem ⋮ Settlement Fund Circulation Problem ⋮ More on the complexity of common superstring and supersequence problems ⋮ Superstrings with multiplicities ⋮ New algorithms for the LCS problem ⋮ Computing minimum length representations of sets of words of uniform length
Cites Work
This page was built for publication: On finding minimal length superstrings
