Article ISI SCOPUS
ACM Transactions on Algorithms  (2020)

Point-Width and Max-CSPs

Carbonnel, Clement; Romero, Miguel; Zivny, Stanislav; Åivný, Stanislav

Abstract

The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs, beta-acyclicity and bounded (incidence) MIM-width, are incomparable and lead to very different algorithms.

Más información

Título según WOS: Point-Width and Max-CSPs
Título según SCOPUS: ID SCOPUS_ID:85092564416 Not found in local SCOPUS DB
Título de la Revista: ACM Transactions on Algorithms
Volumen: 16
Editorial: ASSOC COMPUTING MACHINERY
Fecha de publicación: 2020
DOI:

10.1145/3409447
Notas: ISI, SCOPUS