Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions
From MaRDI portal
Publication:334238
DOI10.1007/s10559-016-9837-yzbMath1348.90655OpenAlexW2406091340MaRDI QIDQ334238
Publication date: 1 November 2016
Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10559-016-9837-y
APX-hardnesspolynomial-time approximation scheme (PTAS)gap-introducing reductiongap-preserving reductionmultiple reoptimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Steiner tree reoptimization in graphs with sharpened triangle inequality
- On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
- A survey on combinatorial optimization in dynamic environments
- Knowing All Optimal Solutions Does Not Help for TSP Reoptimization
- On the Hardness of Reoptimization with Multiple Given Solutions
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- P-Complete Approximation Problems
- On the Hardness of Reoptimization
This page was built for publication: Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions
