Reoptimization of Steiner trees: changing the terminal set

DOI10.1016/j.tcs.2008.04.039zbMath1192.68471OpenAlexW1977823240MaRDI QIDQ838156

Richard Královič, Hans-Joachim Böckenhauer, Tobias Mömke, Peter Rossmanith, Juraj Hromkovič

Publication date: 21 August 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-41948

zbMATH Keywords

approximation algorithmsSteiner treereoptimization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Theory of operating systems (68N25)

Related Items (19)

A survey on combinatorial optimization in dynamic environments ⋮ Reoptimization of maximum weight induced hereditary subgraph problems ⋮ Robust reoptimization of Steiner trees ⋮ On the parameterized complexity of dynamic problems ⋮ Steiner tree reoptimization in graphs with sharpened triangle inequality ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ Reoptimization of NP-Hard Problems ⋮ Unnamed Item ⋮ Reoptimization of Steiner Trees ⋮ Reoptimization of the shortest common superstring problem ⋮ Reoptimization in machine scheduling ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ Knowing All Optimal Solutions Does Not Help for TSP Reoptimization ⋮ Reoptimization of the metric deadline TSP ⋮ Reoptimization of the Metric Deadline TSP ⋮ On the Hardness of Reoptimization ⋮ Reoptimization of the Shortest Common Superstring Problem ⋮ New Reoptimization Techniques applied to Steiner Tree Problem ⋮ REOPTIMIZATION UNDER VERTEX INSERTION: MAX P_k-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Steiner problem with edge lengths 1 and 2
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• Reoptimizing the traveling salesman problem
• A Faster Algorithm for the Steiner Tree Problem
• The steiner problem in graphs
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Steiner tree problems

This page was built for publication: Reoptimization of Steiner trees: changing the terminal set