Zobrazeno 1 - 10
of 51
pro vyhledávání: '"Benoit Larose"'
Publikováno v:
Logical Methods in Computer Science, Vol Volume 3, Issue 4 (2007)
We describe simple algebraic and combinatorial characterisations of finite relational core structures admitting finitely many obstructions. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first
Externí odkaz:
https://doaj.org/article/3ec3983f0f404c699076926fdd5fd768
Autor:
Mark Siggers, Benoit Larose
Publikováno v:
SIAM Journal on Discrete Mathematics. 32:728-749
We find a set of generators of the variety of reflexive digraphs admitting $k-{NU}$ polymorphisms. We do this, in spite of the fact that such digraphs do not have finite tree duality, by defining finite duals of infinite trees. As a result of this, w
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9de5b3229355267fdcfcb87ac906913c
https://doi.org/10.1137/16m110527x
https://doi.org/10.1137/16m110527x
Publikováno v:
Journal of Combinatorial Theory, Series B
The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3380006ad54287e7899fd10fc470da47
http://arxiv.org/abs/1901.04398
http://arxiv.org/abs/1901.04398
Publikováno v:
SIAM Journal on Discrete Mathematics. 27:1940-1963
We describe a generating set for the variety of reflexive graphs that admit a compatible $k$-ary near-unanimity (NU) operation. We further delineate a very simple subset that generates the variety of $j$-absolute retracts; in particular we show that
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e3ddddfae52ffb0bcdb44506f2f2ec21
https://doi.org/10.1137/120894312
https://doi.org/10.1137/120894312
Autor:
Benoit Larose, Hubie Chen
The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. One formulation of the CSP is a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9002aedef486251ff881ca3bf79d437d
http://arxiv.org/abs/1604.00932
http://arxiv.org/abs/1604.00932
Publikováno v:
International Journal of Algebra and Computation. 19:647-668
We say that a finite algebra 𝔸 = 〈A; F〉 has the ability to count if there are subalgebras C of 𝔸3 and Z of 𝔸 such that the structure 〈A; C, Z〉 has the ability to count in the sense of Feder and Vardi. We show that for a core relation
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::308767a5fd44fb3840ab2499afa964a4
https://doi.org/10.1142/s021819670900524x
https://doi.org/10.1142/s021819670900524x
Autor:
Benoit Larose, Gábor Kun
Publikováno v:
European Journal of Combinatorics. 30:17-29
We prove an analog of results by Erdős-Ko-Rado and Greenwell-Lovász by characterising the maximum stable sets in special vertex-transitive subgraphs of powers of complete graphs, and proving that these graphs admit a unique optimal vertex colouring
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fe196a8cb5f2119d6cd638fc8b97f462
https://doi.org/10.1016/j.ejc.2008.03.002
https://doi.org/10.1016/j.ejc.2008.03.002
Autor:
Benoit Larose, Andrei Krokhin
Publikováno v:
Algebra universalis. 59:237-241
A sublattice in a lattice is called supermodular if, for every two elements, one of which belongs to the sublattice, at least one of their meet and join also belongs to the sublattice. In this note, we describe supermodular sublattices in products of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2225749c18d24d833268eb2db906983d
https://doi.org/10.1007/s00012-008-2123-8
https://doi.org/10.1007/s00012-008-2123-8
Autor:
Benoit Larose, Andrei Krokhin
Publikováno v:
SIAM journal on discrete mathematics, 2008, Vol.22(1), pp.312-328 [Peer Reviewed Journal]
Recently, a strong link has been discovered between supermodularity on lattices and tractability of optimization problems known as maximum constraint satisfaction problems. This paper strengthens this link. We study the problem of maximizing a superm
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::87c3ba4e69781d61baec265237eba1f4
https://doi.org/10.1137/060669565
https://doi.org/10.1137/060669565
Autor:
Benoit Larose, László Zádori
Publikováno v:
Algebra universalis. 56:439-466
Let \({\mathcal A}\) be finite relational structure of finite type, and let CSP\({(\mathcal A)}\) denote the following decision problem: if \({\mathcal I}\) is a given structure of the same type as \({\mathcal A}\) , is there a homomorphism from \({\
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3b0c38b27062b0465af5d506b5dd50e5
https://doi.org/10.1007/s00012-007-2012-6
https://doi.org/10.1007/s00012-007-2012-6