On planar valued CSPs

On planar valued CSPs

अन्य संस्करण दिखाएं (1)

We study the computational complexity of planar valued constraint satisfaction problems (VCSPs). First, we show that intractable Boolean VCSPs have to be self-complementary to be tractable in the planar setting, thus extending a corresponding result of Dvořák and Kupec [ICALP’15] from CSPs to VCSPs....

पूर्ण विवरण

ग्रंथसूची विवरण
मुख्य लेखकों:	Fulla, P, Zivny, S
स्वरूप:	Conference item
प्रकाशित:	Dagstuhl Publishing 2016

समान संसाधन

On planar valued CSPs
द्वारा: Fulla, P, और अन्य
प्रकाशित: (2017)

The complexity of Boolean surjective general-valued CSPs
द्वारा: Fulla, P, और अन्य
प्रकाशित: (2017)

The complexity of Boolean surjective general-valued CSPs
द्वारा: Fulla, P, और अन्य
प्रकाशित: (2017)

The complexity of Boolean surjective general-valued CSPs
द्वारा: Fulla, P, और अन्य
प्रकाशित: (2018)

The complexity of finite-valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2016)

The complexity of conservative valued CSPs
द्वारा: Kolmogorov, V, और अन्य
प्रकाशित: (2012)

The complexity of conservative valued CSPs
द्वारा: Kolmogorov, V, और अन्य
प्रकाशित: (2011)

The complexity of conservative valued CSPs
द्वारा: Kolmogorov, V, और अन्य
प्रकाशित: (2013)

The Complexity of Finite-Valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2013)

The complexity of finite-valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2013)

The Power of Linear Programming for Valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2012)

The power of linear programming for valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2015)

The power of linear programming for valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2012)

The complexity of conservative finite-valued CSPs
द्वारा: Kolmogorov, V, और अन्य
प्रकाशित: (2010)

Sherali-Adams relaxations for valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2015)

Necessary conditions for tractability of valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2015)

PTAS for sparse general-valued CSPs
द्वारा: Mezei, BF, और अन्य
प्रकाशित: (2021)

PTAS for sparse general-valued CSPs
द्वारा: Mezei, B, और अन्य
प्रकाशित: (2023)

The limits of SDP relaxations for general-valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2018)

The limits of SDP relaxations for general-valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2017)

Sparsification of binary CSPs
द्वारा: Butti, S, और अन्य
प्रकाशित: (2020)

Sparsification of Binary CSPs
द्वारा: Butti, S, और अन्य
प्रकाशित: (2019)

The power of Sherali-Adams relaxations for general-valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2015)

The power of Sherali-Adams relaxations for general-valued CSPs
द्वारा: Thapper, J, और अन्य
प्रकाशित: (2017)

Additive sparsification of CSPs
द्वारा: Pelleg, E, और अन्य
प्रकाशित: (2021)

Additive sparsification of CSPs
द्वारा: Pelleg, E, और अन्य
प्रकाशित: (2023)

The complexity of general-valued CSPs seen from the other side
द्वारा: Carbonnel, C, और अन्य
प्रकाशित: (2018)

Point-width and max-CSPs
द्वारा: Carbonnel, C, और अन्य
प्रकाशित: (2019)

Point-width and Max-CSPs
द्वारा: Carbonnel, C, और अन्य
प्रकाशित: (2020)

Pliability and approximating max-CSPs
द्वारा: Romero, M, और अन्य
प्रकाशित: (2023)

Treewidth-pliability and PTAS for Max-CSPs
द्वारा: Romero, M, और अन्य
प्रकाशित: (2021)

CLAP: A new algorithm for promise CSPs
द्वारा: Ciardo, L, और अन्य
प्रकाशित: (2023)

On singleton arc consistency for CSPs defined by monotone patterns
द्वारा: Carbonnel, C, और अन्य
प्रकाशित: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
द्वारा: Carbonnel, C, और अन्य
प्रकाशित: (2018)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
द्वारा: Cooper, M, और अन्य
प्रकाशित: (2016)

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
द्वारा: Cooper, M, और अन्य
प्रकाशित: (2017)

Tractable classes of binary CSPs defined by excluded topological minors
द्वारा: Cohen, D, और अन्य
प्रकाशित: (2015)

Small Promise CSPs that reduce to large CSPs
द्वारा: Alexandr Kazda, और अन्य
प्रकाशित: (2022-08-01)

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
द्वारा: Martin C. Cooper, और अन्य
प्रकाशित: (2017-12-01)

A Galois connection for valued constraint languages of infinite size
द्वारा: Fulla, P, और अन्य
प्रकाशित: (2015)