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)