DP-Complete Problems Derived from Extremal NP-Complete Properties
From MaRDI portal
Publication:3182925
DOI10.1007/978-3-642-03816-7_18zbMath1250.68118OpenAlexW1598867843MaRDI QIDQ3182925
Yi Cao, Lorna K. Stewart, Joseph C. Culberson
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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact complexity of exact-four-colorability
- The complexity of facets (and some facets of complexity)
- The complexity of facets resolved
- Some simplified NP-complete graph problems
- On the complexity of non-unique probe selection
- On the complexity of unfrozen problems
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
- Many hard examples for resolution
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Mathematical Foundations of Computer Science 2005