Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions

DOI10.1007/S10559-016-9837-YMaRDI QIDQ334238zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

APX-hardnessgap-introducing reductiongap-preserving reductionmultiple reoptimizationpolynomial-time approximation scheme (PTAS)

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60)

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

Cites work

• scientific article; zbMATH DE number 5859273 (Why is no real title available?)
• scientific article; zbMATH DE number 3907787 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A survey on combinatorial optimization in dynamic environments
• Complexity and approximation in reoptimization
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Knowing all optimal solutions does not help for TSP reoptimization
• On the Hardness of Reoptimization
• On the Hardness of Reoptimization with Multiple Given Solutions
• On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
• P-Complete Approximation Problems
• Steiner tree reoptimization in graphs with sharpened triangle inequality

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)