Reoptimization of the Shortest Common Superstring Problem

DOI10.1007/978-3-642-02441-2_8MaRDI QIDQ3637106zbMATH OpenOpenAlexFDO

Authors D. Bilò, Dennis Komm, Richard Královič, Tobias Mömke, Sebastian Seibert, Anna Zych, Hans-Joachim Böckenhauer

Publication date 7 July 2009

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02441-2_8

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Reoptimization of the shortest common superstring problem
• The shortest superstring problem
• Reoptimization of NP-Hard Problems
• Approximating Shortest Superstrings
• Approximation algorithms for the shortest common superstring problem

Cites work

• A greedy approximation algorithm for constructing shortest common superstrings
• Algorithmic aspects of bioinformatics. Translated from the German original
• Mathematical Foundations of Computer Science 2005
• On finding minimal length superstrings
• On the Hardness of Reoptimization
• On the complexity of postoptimality analysis of 0/1 programs
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimization of Steiner Trees
• Reoptimization of Steiner trees: changing the terminal set
• Reoptimization of Weighted Graph and Covering Problems
• Reoptimization of the Metric Deadline TSP
• Reoptimizing the 0-1 knapsack problem
• Reoptimizing the traveling salesman problem
• Scheduling with forbidden sets
• \boldmath A 2\frac12-Approximation Algorithm for Shortest Superstring

Cited in

(12)

• Reoptimization of the shortest common superstring problem
• scientific article; zbMATH DE number 5074400 (Why is no real title available?)
• A survey on combinatorial optimization in dynamic environments
• Algorithms for Three Versions of the Shortest Common Superstring Problem
• Greedy algorithms for the shortest common superstring that are asymtotically optimal
• New reoptimization techniques applied to Steiner tree problem
• Steiner tree reoptimization in graphs with sharpened triangle inequality
• A theory and algorithms for combinatorial reoptimization
• Approximation algorithms for the shortest common superstring problem
• A Probabilistic PTAS for Shortest Common Superstring
• Reoptimization of the metric deadline TSP
• Knowing all optimal solutions does not help for TSP reoptimization

This page was built for publication: Reoptimization of the Shortest Common Superstring Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637106)