Browsing Departament de Tecnologies de la Informació i les Comunicacions by Author "Butti, Silvia"

Now showing items 1-3 of 3

Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the constraint satisfaction problem

Butti, Silvia; Dalmau, Víctor (Dagstuhl Publishing, 2021)

Given a pair of graphs 𝐀 and 𝐁, the problems of deciding whether there exists either a homomorphism or an isomorphism from 𝐀 to 𝐁 have received a lot of attention. While graph homomorphism is known to be NP-complete, ...
Sparsification of binary CSPs

Butti, Silvia; Stanislav Zivný (SIAM (Society for Industrial and Applied Mathematics), 2020)

A cut ε-sparsifier of a weighted graph G is a re-weighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of ε. Since their intro- duction by Bencz´ur and Karger ...
The complexity of the distributed constraint satisfaction problem

Butti, Silvia; Dalmau, Víctor (SpringerOpen, 2022)

We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which ...

Now showing items 1-3 of 3

Search DSpace

In collaboration with Compliant to Partaking