The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings

DOI10.1016/j.dam.2015.06.003zbMath1350.68289OpenAlexW817371852MaRDI QIDQ313766

Eric Rivals, Bastien Cazaux

Publication date: 12 September 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.06.003

zbMATH Keywords

data compressionapproximation algorithmstringologyassemblygreedy conjectureshortest superstring problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (4)

A linear time algorithm for shortest cyclic cover of strings ⋮ Relationship between superstring and compression measures: new insights on the greedy conjecture ⋮ Superstring Graph: A New Approach for Genome Assembly ⋮ Superstrings with multiplicities

Cites Work

• The greedy algorithm for shortest superstrings
• A greedy approximation algorithm for constructing shortest common superstrings
• On finding minimal length superstrings
• Acquisition of 2D shape models from scenes with overlapping objects using string matching
• Approximation algorithms for the shortest common superstring problem
• Approximating maximum weight cycle covers in directed graphs with weights zero and one
• On the Greedy Superstring Conjecture
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• The greedy travelling salesman's problem
• Algorithms on Strings, Trees and Sequences
• Rotations of Periodic Strings and Short Superstrings
• Greedy in Approximation Algorithms
• Unnamed Item

This page was built for publication: The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings