Reoptimization of Weighted Graph and Covering Problems

DOI10.1007/978-3-540-93980-1_16zbMath1209.68632OpenAlexW1508327628MaRDI QIDQ3602840

Davide Bilò, Anna Zych, Peter Widmayer

Publication date: 12 February 2009

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-93980-1_16

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation algorithms (68W25)

Related Items (16)

A survey on combinatorial optimization in dynamic environments ⋮ 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 ⋮ Steiner tree reoptimization in graphs with sharpened triangle inequality ⋮ Reoptimization of NP-Hard Problems ⋮ Unnamed Item ⋮ Reoptimization of the shortest common superstring problem ⋮ Reoptimization in machine scheduling ⋮ A note on the traveling salesman reoptimization problem under vertex insertion ⋮ Parameterized Dynamic Variants of Red-Blue Dominating Set ⋮ Knowing All Optimal Solutions Does Not Help for TSP Reoptimization ⋮ Reoptimization of the metric deadline TSP ⋮ Fast reoptimization for the minimum spanning tree problem ⋮ Reoptimization of the Shortest Common Superstring Problem ⋮ New Reoptimization Techniques applied to Steiner Tree Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Approximating maximum independent sets by excluding subgraphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Reoptimization of Steiner Trees
• Reoptimizing the traveling salesman problem
• On the Hardness of Reoptimization
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours

This page was built for publication: Reoptimization of Weighted Graph and Covering Problems