Krokhin, Andrei; Opršal, Jakub; Wrochna, Marcin; Živný, Stanislav Topology and adjunction in promise constraint satisfaction. (English) Zbl 07672224 SIAM J. Comput. 52, No. 1, 38-79 (2023). MSC: 68Q17 68Q25 68R05 05C15 PDFBibTeX XMLCite \textit{A. Krokhin} et al., SIAM J. Comput. 52, No. 1, 38--79 (2023; Zbl 07672224) Full Text: DOI arXiv
Krokhin, Andrei; Zivny, Stanislav The complexity of valued CSPs. (English) Zbl 1482.68165 Krokhin, Andrei (ed.) et al., The constraint satisfaction problem: complexity and approximability, Dagstuhl seminar 15301, July 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. Dagstuhl Follow-Ups 7, 233-266 (2017). MSC: 68R07 68Q25 68Q27 90C27 PDFBibTeX XMLCite \textit{A. Krokhin} and \textit{S. Zivny}, Dagstuhl Follow-Ups 7, 233--266 (2017; Zbl 1482.68165) Full Text: DOI
Barto, Libor; Krokhin, Andrei; Willard, Ross Polymorphisms, and how to use them. (English) Zbl 1482.68161 Krokhin, Andrei (ed.) et al., The constraint satisfaction problem: complexity and approximability, Dagstuhl seminar 15301, July 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. Dagstuhl Follow-Ups 7, 1-44 (2017). MSC: 68R07 08A70 68Q25 PDFBibTeX XMLCite \textit{L. Barto} et al., Dagstuhl Follow-Ups 7, 1--44 (2017; Zbl 1482.68161) Full Text: DOI
Cohen, David A.; Cooper, Martin C.; Jeavons, Peter G.; Krokhin, Andrei; Powell, Robert; Živný, Stanislav Binarisation for valued constraint satisfaction problems. (English) Zbl 1477.68121 SIAM J. Discrete Math. 31, No. 4, 2279-2300 (2017). MSC: 68Q25 08A70 68Q17 PDFBibTeX XMLCite \textit{D. A. Cohen} et al., SIAM J. Discrete Math. 31, No. 4, 2279--2300 (2017; Zbl 1477.68121) Full Text: DOI arXiv
Egri, László; Krokhin, Andrei; Larose, Benoit; Tesson, Pascal The complexity of the list homomorphism problem for graphs. (English) Zbl 1322.68100 Theory Comput. Syst. 51, No. 2, 143-178 (2012). Reviewer: Guillaume Fertin (Nantes) MSC: 68Q25 05C25 05C60 68Q17 PDFBibTeX XMLCite \textit{L. Egri} et al., Theory Comput. Syst. 51, No. 2, 143--178 (2012; Zbl 1322.68100) Full Text: DOI Link
Jonsson, Peter; Krokhin, Andrei; Kuivinen, Fredrik Hard constraint satisfaction problems have hard gaps at location 1. (English) Zbl 1176.90498 Theor. Comput. Sci. 410, No. 38-40, 3856-3874 (2009). MSC: 90C27 68W25 68Q17 PDFBibTeX XMLCite \textit{P. Jonsson} et al., Theor. Comput. Sci. 410, No. 38--40, 3856--3874 (2009; Zbl 1176.90498) Full Text: DOI
Bulatov, Andrei A.; Krokhin, Andrei; Larose, Benoit Dualities for constraint satisfaction problems. (English) Zbl 1171.68494 Creignou, Nadia (ed.) et al., Complexity of constraints. An overview of current research themes. Berlin: Springer (ISBN 978-3-540-92799-0/pbk). Lecture Notes in Computer Science 5250, 93-124 (2008). MSC: 68Q25 03B70 08A70 PDFBibTeX XMLCite \textit{A. A. Bulatov} et al., Lect. Notes Comput. Sci. 5250, 93--124 (2008; Zbl 1171.68494) Full Text: DOI
Jonsson, Peter; Krokhin, Andrei Computational complexity of auditing finite attributes in statistical databases. (English) Zbl 1140.68016 J. Comput. Syst. Sci. 74, No. 5, 898-909 (2008). MSC: 68P15 68Q25 PDFBibTeX XMLCite \textit{P. Jonsson} and \textit{A. Krokhin}, J. Comput. Syst. Sci. 74, No. 5, 898--909 (2008; Zbl 1140.68016) Full Text: DOI
Dalmau, Víctor; Krokhin, Andrei Majority constraints have bounded pathwidth duality. (English) Zbl 1138.68052 Eur. J. Comb. 29, No. 4, 821-837 (2008). MSC: 68T20 68T27 PDFBibTeX XMLCite \textit{V. Dalmau} and \textit{A. Krokhin}, Eur. J. Comb. 29, No. 4, 821--837 (2008; Zbl 1138.68052) Full Text: DOI Link
Dalmau, Víctor; Krokhin, Andrei; Larose, Benoit Retractions onto series-parallel posets. (English) Zbl 1141.06001 Discrete Math. 308, No. 11, 2104-2114 (2008). Reviewer: Jiří Rachůnek (Olomouc) MSC: 06A06 PDFBibTeX XMLCite \textit{V. Dalmau} et al., Discrete Math. 308, No. 11, 2104--2114 (2008; Zbl 1141.06001) Full Text: DOI Link
Jonsson, Peter; Krokhin, Andrei Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights. (English) Zbl 1115.68143 J. Comput. Syst. Sci. 73, No. 5, 691-702 (2007). MSC: 68T20 68R10 05C15 68Q25 PDFBibTeX XMLCite \textit{P. Jonsson} and \textit{A. Krokhin}, J. Comput. Syst. Sci. 73, No. 5, 691--702 (2007; Zbl 1115.68143) Full Text: DOI
Jonsson, Peter; Krokhin, Andrei Recognizing frozen variables in constraint satisfaction problems. (English) Zbl 1086.68056 Theor. Comput. Sci. 329, No. 1-3, 93-113 (2004). MSC: 68Q25 68T20 PDFBibTeX XMLCite \textit{P. Jonsson} and \textit{A. Krokhin}, Theor. Comput. Sci. 329, No. 1--3, 93--113 (2004; Zbl 1086.68056) Full Text: DOI