Topology and adjunction in promise constraint satisfaction
The approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction probl...
| Príomhchruthaitheoirí: | , , , |
|---|---|
| Formáid: | Journal article |
| Teanga: | English |
| Foilsithe / Cruthaithe: |
Society for Industrial and Applied Mathematics
2023
|