Back to B. Larose's Home Page
 

Publications

Ph.D. Thesis:

Opérations isotones: critčre de complétude,  propriétés du point fixe et de projection,  Université de Montréal, 1993, 128 pages.

Refereed Publications:

(with M. Siggers) Strongly irreducible reflexive digraphs; in preparation.
(with M. Siggers) NU polymorphisms on reflexive digraphs, 24 pages, SIAM J. Discrete Math., to appear. PDF
(with H. Chen) Asking the metaquestions in constraint tractability,  ACM Transactions on Computation Theory, 30 pages, to appear. http://arxiv.org/abs/1604.00932
Algebraic Methods and the Complexity of Digraph CSPs, a Survey, in: The Constraint Satisfaction Problem: Complexity and Approximability, Andrei A. Krokhin, Stanislav Zivny, eds. Dagstuhl Follow-Ups 7, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2017, 267–285. PDF
(with  V. Dalmau, L. Egri, P. Hell, A. Rafiey) Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy. LICS 2015.
(with  T. Feder, P. Hell, M. Siggers, C. Tardif) Graphs admitting k-NU operations. Part II: Irreflexive Graphs,  SIAM J. Discrete Math., 28, no. 2, 817-834, 2014. 
(with  L. Egri, P. Hell, A. Rafiey) Space complexity of list H-coloring: a dichotomy, (updated version), 23 pages, SODA 2014.  
(with A. Lemaitre), List-Homomorphism Problems on Graphs and Arc-Consistency, Discrete Math., 313, no. 22, 2525–2537, 2013. 
(with  T. Feder, P. Hell, C. Loten, M. Siggers, C. Tardif) Graphs admitting k-NU operations. Part I: Reflexive Graphs, SIAM J. Discrete Math, 27, no. 4, 1940-1963, 2013. 
(with A. Lemaitre), List-Homomorphism Problems on Graphs and Arc-Consistency, ISMVL 2012, 343-348, 2012. 
(with L. Egri, A. Krokhin, P. Tesson) The complexity of list homomorphism problems for graphs,
Theoret. Comput. Sci., Vol. 51 (special issue for selected papers from STACS 2010), Issue 2, 143-178, 2012.      (Best of 2012, Notable Paper, Computing Reviews ACM )
(with L. Egri, A. Krokhin, P. Tesson), The complexity of list homomorphism problems for graphs, STACS 2010.  
(with M. Desgroseilliers, C. Malvenuto and C. Vincent), Some results on two conjectures of Schützenberger, (12 pages), Canad. Math. Bull., Vol. 53,  no. 3,  453-465, 2010. 
(with M.Valeriote and L. Zádori), Omitting types, bounded width and the ability to count, Internat. J. Algebra Comput., 19, No. 5, 647–668, 2009.  
(with P. Tesson) Universal Algebra and Hardness Results for Constraint Satisfaction Problems,   Theoret. Comput. Sci.
(Special issue for selected papers from ICALP'07), 410, 1629-1647, 2009.  
(with G. Kun), Stable sets of maximal size in orbits of powers of K_n, European Journal of Combinatorics 30  17–29, 2009.
(with A. Bulatov and  A. Krokhin), Dualities for Constraint Satisfaction Problems, In: Complexity of Constraints, LNCS 5250, 93-124, 2008. 
(with  A. Krokhin),  A note on supermodular sublattices in  finite relatively complemented lattices,   Algebra Universalis,  59  no. 1-2,  237--241, 2008. 
(with  A. Krokhin), Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction,
 SIAM J. on Discrete Math.
22  no. 1,  312-328, 2008. 
(with V. Dalmau and A. Krokhin), Retractions onto series-parallel posets, Discrete Math.308   no. 11,  2104-2114, 2008.   
(with L. Haddad), Colourings of hypergraphs, permutation groups ans CSP's, Logic Colloquium '04, 93-108,  Lect. Notes Log., 27,
Assoc. Symbol. Logic, La Jolla, CA,
2008. 
(with L. Egri, P. Tesson), Directed st-Connectivity is not definable in symmetric Datalog, ICALP 2008.
(with V. Dalmau), Maltsev + Datalog -> Symmetric Datalog, (10 pages),  LICS 2008. P
(with C. Loten and C. Tardif),  A characterisation of first-order Constraint Satisfaction Problems,
Logical Methods in Computer Science (Special issue: selected contributions of LICS '06),  3 (4), 2007.  
(with P. Tesson) Universal Algebra and Hardness Results for Constraint Satisfaction Problems, (12 pages), ICALP 2007. 
(with L. Egri, P. Tesson), Symmetric Datalog and Constraint Satisfaction Problems in Logspace, (10 pages), LICS 2007. 
(with L. Zádori), Bounded width problems and algebras, Algebra Universalis, 56  no. 3-4, 439-466, 2007. 
(with V. Dalmau and A. Krokhin), First-order definable retraction problems for posets and reflexive graphs, J. Logic Comput. 17, no. 1, 31-51, 2007. 
(with C. Loten and C. Tardif),  A characterisation of first-order Constraint Satisfaction Problems, in Proceedings of
the 21st IEEE Symposium on Logic in Computer Science (LICS 2006), IEEE,  201-210, 2006.
(with O. Klíma and P. Tesson), Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture,
in Mathematical Foundations of Computer Science 2006 (MFCS 2006), Lecture Notes in Computer Science 4162, 584--595, 2006.  
(with L. Zádori), Taylor terms, constraint satisfaction and the complexity of  polynomial equations over finite algebras,
Internat. J. Algebra Comput.
16,  no. 3,  563-581, 2006.
Taylor operations on finite reflexive structures, International Journal of Mathematics and Computer Science, 1, no. 1, 1-26, 2006.
(with A. Krokhin), Maximum constraint satisfaction on diamonds,  in Eleventh International Conference on Principles and Practice of Constraint Programming (CP'05), Lecture Notes in Computer Science 3709, 388-402, 2005.
(with C. Loten and L. Zádori), A polynomial-time algorithm for near-unanimity graphs, J. Algorithms55,  no. 2 , 177-191, 2005.
Isotone analogs of results by  Malt'sev and Rosenberg,  Beiträge Algebra Geom., 46, no. 1 61-70, 2005. 
(with L. Zádori), Finite posets and topological spaces in locally finite varieties,  Algebra Universalis, 52, no. 2-3, 119-136, 2004.
(with V. Dalmau and A. Krokhin), First-order definable retraction problems for posets and reflexive graphs,  in
Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), IEEE,  232-241, 2004. 
(with C. Tardif), A discrete homotopy theory for binary reflexive structures, Adv. Math., 189 (2), 268-300, 2004. 
(with  C. Malvenuto), Stable sets of maximal size in  Kneser-type graphs, Europ. J. Combinatorics, 25 (1),  657-673, 2004.   
(with L. Zádori), The complexity of the extendibility problem for finite posets,   SIAM J. Discrete Math., 17 (1),  114-121, 2003. 
A note on minimal varieties generated by order-primal algebras, Algebra Universalis, 49, 107-109, 2003.  
(with A. Krokhin), Solving order constraints in logarithmic space,  in Proceedings of 20th International Symposium on Theoretical Aspects of Computer Science (STACS'03),  Berlin, Germany, Lecture Notes in Computer Science 2607, 2003, 379-390. 
Families of strongly projective graphs, Discuss. Math. Graph Theory, 22,  271-292, 2002.  
Strongly projective  graphs, Canad. J. Math., 54 (4), 757-768, 2002. 
(with A. Krokhin),  A monoďdal interval of isotone clones on a finite chain,  Acta Sci. Math. (Szeged),68,37-62, 2002.  
(with C. Tardif), Projectivity and independent sets in powers of graphs, J. Graph Theory, 40 (3), 162-171,  2002. 
(with C. Tardif), Strongly rigid graphs and projectivity,  Mult.-Valued Log.7, no. 5-6,  339-362, 2001. 
(with C. Tardif), Hedetniemi's conjecture and the retracts of a product of graphs, Combinatorica, 20 (4) , 531-544, 2000.  
Clone coverings and invertible operations, Mult.-Valued Log., 5, no. 5, 373-390, 2000. 
(with G. Czédli and G. Pollák), Four notes on coalition lattices,Order, Vol. 16, no. 1, 19-29, 1999.
(with F. Laviolette and C. Tardif), Normal Cayley graphs and hom-idempotent graphs, Europ. J. Combinatorics, 19,  867-881, 1998.
(with L. Zádori), Algebraic properties and dismantlability of finite posets, Discrete Math., 163, 89-99, 1997.
On the centralizer of the join operation of a finite lattice, Algebra Universalis, 34, 304-313, 1995.
Minimal automorphic posets and the projection property, Internat. J. Algebra Comput., Vol. 5, no. 1, 65-80, 1995.
A completeness criterion for isotone operations on a finite chain, Acta Sci. Math. (Szeged), 59, 319-356, 1994.
A property of projective ordered sets, Europ. J. Combinatorics, 13, 371-378, 1992.
Sous-clones maximaux du clone des opérations monotones sur un ordre borné fini, C. R. Acad. Sci. Parist. 314, Série I, 245-247, 1992.
Finite projective ordered sets, Order8, 33-40, 1991.
  Back to top of Publications