Reoptimization of Steiner trees: changing the terminal set

DOI10.1016/J.TCS.2008.04.039MaRDI QIDQ838156zbMATH OpenOpenAlexFDO

Authors Hans-Joachim Böckenhauer, Richard Královič, 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)

Recommendations

• Reoptimization of Steiner Trees
• New algorithms for Steiner tree reoptimization
• The Steiner tree reoptimization problem with sharpened triangle inequality (extended abstract)
• Simple and fast reoptimizations for the Steiner tree problem
• Robust reoptimization of Steiner trees

Cites work

• scientific article; zbMATH DE number 5859273 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• A Faster Algorithm for the Steiner Tree Problem
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimizing the traveling salesman problem
• Simple and fast reoptimizations for the Steiner tree problem
• Steiner tree problems
• The Steiner problem with edge lengths 1 and 2
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• The steiner problem in graphs

Cited in

(25)

• Reoptimization under vertex insertion: max \(P_{k}\)-free subgraph and max planar subgraph
• Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
• Reoptimization of the metric deadline TSP
• Robust reoptimization of Steiner trees
• New algorithms for Steiner tree reoptimization
• Reoptimization of the shortest common superstring problem
• Robust reoptimization of Steiner trees
• Knowing all optimal solutions does not help for TSP reoptimization
• Reoptimization of the Metric Deadline TSP
• Reoptimization of Steiner Trees
• New advances in reoptimizing the minimum Steiner tree problem
• Improved approximations for hard optimization problems via problem instance classification
• Reoptimization of NP-Hard Problems
• Steiner tree reoptimization in graphs with sharpened triangle inequality
• Reoptimization of maximum weight induced hereditary subgraph problems
• Reoptimization of the Shortest Common Superstring Problem
• The Steiner tree reoptimization problem with sharpened triangle inequality (extended abstract)
• Reoptimization in machine scheduling
• On the Hardness of Reoptimization
• New reoptimization techniques applied to Steiner tree problem
• A survey on combinatorial optimization in dynamic environments
• Simple and fast reoptimizations for the Steiner tree problem
• On the parameterized complexity of dynamic problems
• Reconfiguration of Steiner trees in an unweighted graph
• New algorithms for Steiner tree reoptimization

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

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