Outputs (2)

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights (2007)
Journal Article
Jonsson, P., & Krokhin, A. (2007). Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. Journal of Computer and System Sciences, 73(5), 691-702. https://doi.org/10.1016/j.jcss.2007.02.001

In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of positive-weight constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so that the total weight... Read More about Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights.

First-order definable retraction problems for posets and reflexive graphs (2007)
Journal Article
Dalmau, V., Krokhin, A., & Larose, B. (2007). First-order definable retraction problems for posets and reflexive graphs. Journal of Logic and Computation, 17(1), 31-51. https://doi.org/10.1093/logcom/exl014

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterzies all posets and all reflexive graphs Q such that the class of all posets... Read More about First-order definable retraction problems for posets and reflexive graphs.