The power of arc consistency for CSPs defined by partially-ordered forbidden patterns

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns

Pokaż inne wersje (1)

Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding patterns (generic subinstances) provides a means of defining CSP fragments which are neither exclusively language-based no...

Szczegółowa specyfikacja

Opis bibliograficzny
Główni autorzy:	Cooper, M, Zivny, S
Format:	Conference item
Wydane:	Association for Computing Machinery 2016

Podobne zapisy

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
od: Cooper, M, i wsp.
Wydane: (2017)

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
od: Martin C. Cooper, i wsp.
Wydane: (2017-12-01)

On singleton arc consistency for CSPs defined by monotone patterns
od: Carbonnel, C, i wsp.
Wydane: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
od: Carbonnel, C, i wsp.
Wydane: (2018)

Tractable classes of binary CSPs defined by excluded topological minors
od: Cohen, D, i wsp.
Wydane: (2015)

The Power of Linear Programming for Valued CSPs
od: Thapper, J, i wsp.
Wydane: (2012)

The power of linear programming for valued CSPs
od: Thapper, J, i wsp.
Wydane: (2015)

The power of linear programming for valued CSPs
od: Thapper, J, i wsp.
Wydane: (2012)

Sparsification of binary CSPs
od: Butti, S, i wsp.
Wydane: (2020)

Sparsification of Binary CSPs
od: Butti, S, i wsp.
Wydane: (2019)

On planar valued CSPs
od: Fulla, P, i wsp.
Wydane: (2016)

Additive sparsification of CSPs
od: Pelleg, E, i wsp.
Wydane: (2021)

Additive sparsification of CSPs
od: Pelleg, E, i wsp.
Wydane: (2023)

On planar valued CSPs
od: Fulla, P, i wsp.
Wydane: (2017)

The power of Sherali-Adams relaxations for general-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2015)

The power of Sherali-Adams relaxations for general-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2017)

The complexity of finite-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2016)

The complexity of conservative valued CSPs
od: Kolmogorov, V, i wsp.
Wydane: (2012)

The complexity of conservative valued CSPs
od: Kolmogorov, V, i wsp.
Wydane: (2011)

The complexity of conservative valued CSPs
od: Kolmogorov, V, i wsp.
Wydane: (2013)

The Complexity of Finite-Valued CSPs
od: Thapper, J, i wsp.
Wydane: (2013)

The complexity of finite-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2013)

Pliability and approximating max-CSPs
od: Romero, M, i wsp.
Wydane: (2023)

Point-width and max-CSPs
od: Carbonnel, C, i wsp.
Wydane: (2019)

Point-width and Max-CSPs
od: Carbonnel, C, i wsp.
Wydane: (2020)

Variable elimination in binary CSP via forbidden patterns
od: Cohen, D, i wsp.
Wydane: (2013)

The complexity of conservative finite-valued CSPs
od: Kolmogorov, V, i wsp.
Wydane: (2010)

Sherali-Adams relaxations for valued CSPs
od: Thapper, J, i wsp.
Wydane: (2015)

Necessary conditions for tractability of valued CSPs
od: Thapper, J, i wsp.
Wydane: (2015)

Treewidth-pliability and PTAS for Max-CSPs
od: Romero, M, i wsp.
Wydane: (2021)

PTAS for sparse general-valued CSPs
od: Mezei, BF, i wsp.
Wydane: (2021)

PTAS for sparse general-valued CSPs
od: Mezei, B, i wsp.
Wydane: (2023)

The complexity of Boolean surjective general-valued CSPs
od: Fulla, P, i wsp.
Wydane: (2017)

CLAP: A new algorithm for promise CSPs
od: Ciardo, L, i wsp.
Wydane: (2023)

The limits of SDP relaxations for general-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2018)

The complexity of Boolean surjective general-valued CSPs
od: Fulla, P, i wsp.
Wydane: (2017)

The limits of SDP relaxations for general-valued CSPs
od: Thapper, J, i wsp.
Wydane: (2017)

The complexity of Boolean surjective general-valued CSPs
od: Fulla, P, i wsp.
Wydane: (2018)

Variable and value elimination in binary constraint satisfaction via forbidden patterns
od: Cohen, DA, i wsp.
Wydane: (2015)

The complexity of general-valued CSPs seen from the other side
od: Carbonnel, C, i wsp.
Wydane: (2018)