Reoptimization of the shortest common superstring problem
From MaRDI portal
Publication:639296
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
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 Pk-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
