Reoptimization of maximum weight induced hereditary subgraph problems
From MaRDI portal
Publication:386899
DOI10.1016/j.tcs.2012.10.037zbMath1277.68085OpenAlexW2085587857MaRDI QIDQ386899
Jérôme Monnot, Nicolas Boria, Vangelis Th. Paschos
Publication date: 11 December 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.10.037
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (6)
A survey on combinatorial optimization in dynamic environments ⋮ On Lagrangian relaxation for constrained maximization and reoptimization problems ⋮ Robust reoptimization of Steiner trees ⋮ Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications ⋮ Unnamed Item ⋮ A note on the traveling salesman reoptimization problem under vertex insertion
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reoptimizing the 0-1 knapsack problem
- Reoptimization of the shortest common superstring problem
- Graph minors. XX: Wagner's conjecture
- Reoptimization of Steiner trees: changing the terminal set
- Fast reoptimization for the minimum spanning tree problem
- Approximating maximum independent sets by excluding subgraphs
- A data structure for dynamic trees
- Reoptimization of the metric deadline TSP
- On finite affine line transitive planes
- New Reoptimization Techniques applied to Steiner Tree Problem
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Knowing All Optimal Solutions Does Not Help for TSP Reoptimization
- On the Hardness of Reoptimization with Multiple Given Solutions
- Reoptimization of Steiner Trees
- The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality
- Reoptimization of Weighted Graph and Covering Problems
- Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Reoptimizing the traveling salesman problem
- Maintaining minimum spanning trees in dynamic graphs
- The approximation of maximum subgraph problems
- Approximating Maximum Clique by Removing Subgraphs
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- On the Hardness of Reoptimization
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- Scheduling with forbidden sets
This page was built for publication: Reoptimization of maximum weight induced hereditary subgraph problems
