On planar valued CSPs
We study the computational complexity of planar valued constraint satisfaction problems (VCSPs), which require the incidence graph of the instance be planar. First, we show that intractable Boolean VCSPs have to be self-complementary to be tractable in the planar setting, thus extending a correspond...
| Հիմնական հեղինակներ: | , |
|---|---|
| Ձևաչափ: | Journal article |
| Հրապարակվել է: |
Elsevier
2017
|