Reoptimization of the shortest common superstring problem

DOI10.1007/s00453-010-9419-8zbMath1238.68189OpenAlexW2031907835MaRDI QIDQ639296

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

Publication date: 20 September 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/182345

zbMATH Keywords

approximation algorithmsreoptimizationshortest common superstring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items

On Lagrangian relaxation for constrained maximization and reoptimization problems ⋮ Reoptimization of maximum weight induced hereditary subgraph problems ⋮ Robust reoptimization of Steiner trees ⋮ Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications ⋮ Reoptimization of NP-Hard Problems ⋮ Unnamed Item ⋮ Fixing improper colorings of graphs ⋮ A note on the traveling salesman reoptimization problem under vertex insertion ⋮ Knowing All Optimal Solutions Does Not Help for TSP Reoptimization ⋮ REOPTIMIZATION UNDER VERTEX INSERTION: MAX P_k-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH ⋮ Superstrings with multiplicities

Cites Work

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