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

Taispeáin leaganacha eile (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...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Cooper, M, Zivny, S
Formáid:	Conference item
Foilsithe / Cruthaithe:	Association for Computing Machinery 2016

Míreanna comhchosúla

The power of arc consistency for CSPs defined by partially-ordered forbidden patterns
de réir: Cooper, M, et al.
Foilsithe / Cruthaithe: (2017)

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
de réir: Martin C. Cooper, et al.
Foilsithe / Cruthaithe: (2017-12-01)

On singleton arc consistency for CSPs defined by monotone patterns
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2018)

On singleton arc consistency for CSPs defined by monotone patterns
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2018)

Tractable classes of binary CSPs defined by excluded topological minors
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2015)

The Power of Linear Programming for Valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2012)

The power of linear programming for valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

The power of linear programming for valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2012)

Sparsification of binary CSPs
de réir: Butti, S, et al.
Foilsithe / Cruthaithe: (2020)

Sparsification of Binary CSPs
de réir: Butti, S, et al.
Foilsithe / Cruthaithe: (2019)

Variable elimination in binary CSP via forbidden patterns
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2013)

On planar valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2016)

Additive sparsification of CSPs
de réir: Pelleg, E, et al.
Foilsithe / Cruthaithe: (2021)

Additive sparsification of CSPs
de réir: Pelleg, E, et al.
Foilsithe / Cruthaithe: (2023)

On planar valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2017)

The power of Sherali-Adams relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

The power of Sherali-Adams relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2017)

The complexity of finite-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2016)

The complexity of conservative valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2012)

The complexity of conservative valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2011)

The complexity of conservative valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2013)

The Complexity of Finite-Valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2013)

The complexity of finite-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2013)

Pliability and approximating max-CSPs
de réir: Romero, M, et al.
Foilsithe / Cruthaithe: (2023)

Point-width and max-CSPs
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2019)

Point-width and Max-CSPs
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2020)

Variable and value elimination in binary constraint satisfaction via forbidden patterns
de réir: Cohen, DA, et al.
Foilsithe / Cruthaithe: (2015)

The complexity of conservative finite-valued CSPs
de réir: Kolmogorov, V, et al.
Foilsithe / Cruthaithe: (2010)

Sherali-Adams relaxations for valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

Necessary conditions for tractability of valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2015)

Treewidth-pliability and PTAS for Max-CSPs
de réir: Romero, M, et al.
Foilsithe / Cruthaithe: (2021)

PTAS for sparse general-valued CSPs
de réir: Mezei, BF, et al.
Foilsithe / Cruthaithe: (2021)

PTAS for sparse general-valued CSPs
de réir: Mezei, B, et al.
Foilsithe / Cruthaithe: (2023)

The complexity of Boolean surjective general-valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2017)

CLAP: A new algorithm for promise CSPs
de réir: Ciardo, L, et al.
Foilsithe / Cruthaithe: (2023)

The limits of SDP relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2018)

The complexity of Boolean surjective general-valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2017)

The limits of SDP relaxations for general-valued CSPs
de réir: Thapper, J, et al.
Foilsithe / Cruthaithe: (2017)

The complexity of Boolean surjective general-valued CSPs
de réir: Fulla, P, et al.
Foilsithe / Cruthaithe: (2018)

The complexity of general-valued CSPs seen from the other side
de réir: Carbonnel, C, et al.
Foilsithe / Cruthaithe: (2018)