Steiner tree reoptimization in graphs with sharpened triangle inequality
From MaRDI portal
Publication:414457
DOI10.1016/j.jda.2011.03.014zbMath1238.68105OpenAlexW2042882430MaRDI QIDQ414457
Hans-Joachim Böckenhauer, Karin Freiermuth, Björn Steffen, Tobias Mömke, Andreas Sprock, Juraj Hromkovič
Publication date: 11 May 2012
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2011.03.014
Related Items
Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions ⋮ Robust reoptimization of Steiner trees ⋮ Submodular reassignment problem for reallocating agents to tasks with synergy effects ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ Unnamed Item ⋮ A note on the traveling salesman reoptimization problem under vertex insertion
Cites Work
- Approximation algorithms for the TSP with sharpened triangle inequality
- Reoptimizing the 0-1 knapsack problem
- Reoptimization of Steiner trees: changing the terminal set
- The Steiner problem with edge lengths 1 and 2
- The Steiner tree problem
- On the approximability of the Steiner tree problem in phylogeny
- A threshold of ln n for approximating set cover
- Reoptimization of Steiner Trees
- Reoptimization of the Metric Deadline TSP
- Reoptimization of Weighted Graph and Covering Problems
- Reoptimization of the Shortest Common Superstring Problem
- Reoptimizing the traveling salesman problem
- Approximating Steiner trees in graphs with restricted weights
- On the Hardness of Reoptimization
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- Scheduling with forbidden sets
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
