Article ISI SCOPUS
ACM TRANSACTIONS ON ALGORITHMS  (2020)

Point-Width and Max-CSPs

Romero, Miguel

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: Point-Width and Max-CSPs
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