DP-Complete Problems Derived from Extremal NP-Complete Properties

DOI10.1007/978-3-642-03816-7_18MaRDI QIDQ3182925zbMATH OpenOpenAlexFDO

Authors Yi Cao, J. Culberson, Lorna Stewart

Publication date 16 October 2009

Published in Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03816-7_18

zbMATH Keywords

colorabilitycomplexityDP-completeextremal problemimplicantunfrozen

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 3890729
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
• On the complexity of unfrozen problems
• scientific article; zbMATH DE number 4024813
• Taking it to the limit: On infinite variants of NP-complete problems

Cites work

• Exact complexity of exact-four-colorability
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
• scientific article; zbMATH DE number 4024813 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Many hard examples for resolution
• Mathematical Foundations of Computer Science 2005
• On the complexity of non-unique probe selection
• On the complexity of unfrozen problems
• Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete
• Some simplified NP-complete graph problems
• The complexity of facets (and some facets of complexity)
• The complexity of facets resolved
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth

Cited in

(5)

• MPF problem over modified medial semigroup is NP-complete
• On the complexity of unfrozen problems
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
• scientific article; zbMATH DE number 3890729 (Why is no real title available?)
• On Some $\mathcal{NP}$ -complete SEFE Problems

This page was built for publication: DP-Complete Problems Derived from Extremal NP-Complete Properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3182925)