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-YzbMATH Open1348.90655OpenAlexW2406091340MaRDI QIDQ334238FDOQ334238
Authors: Victor A. Mikhailyuk 
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
Recommendations
- On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
- Reoptimization of NP-Hard Problems
- On the hardness of approximating the chromatic number
- Reoptimization of maximum weight induced hereditary subgraph problems
- On the Hardness of Reoptimization
APX-hardnessgap-introducing reductiongap-preserving reductionmultiple reoptimizationpolynomial-time approximation scheme (PTAS)
Cites Work
- Title not available (Why is that?)
- P-Complete Approximation Problems
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Complexity and approximation in reoptimization
- A survey on combinatorial optimization in dynamic environments
- Knowing all optimal solutions does not help for TSP reoptimization
- Title not available (Why is that?)
- On the Hardness of Reoptimization with Multiple Given Solutions
- Title not available (Why is that?)
- Steiner tree reoptimization in graphs with sharpened triangle inequality
- On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334238)
