Gerasimova, Olga; Kikot, Stanislav; Kurucz, Agi; Podolskii, Vladimir; Zakharyaschev, Michael A tetrachotomy of ontology-mediated queries with a covering axiom. (English) Zbl 07554486 Artif. Intell. 309, Article ID 103738, 46 p. (2022). MSC: 68T30 PDFBibTeX XMLCite \textit{O. Gerasimova} et al., Artif. Intell. 309, Article ID 103738, 46 p. (2022; Zbl 07554486) Full Text: DOI arXiv
Hell, Pavol; Nešetřil, Jaroslav In praise of homomorphisms. (English) Zbl 1506.08001 Comput. Sci. Rev. 40, Article ID 100352, 5 p. (2021). MSC: 08A05 08-03 PDFBibTeX XMLCite \textit{P. Hell} and \textit{J. Nešetřil}, Comput. Sci. Rev. 40, Article ID 100352, 5 p. (2021; Zbl 1506.08001) Full Text: DOI
Matl, Gregor; Živný, Stanislav Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs. (English) Zbl 1494.68202 Algorithmica 82, No. 12, 3492-3520 (2020). MSC: 68R10 68R07 PDFBibTeX XMLCite \textit{G. Matl} and \textit{S. Živný}, Algorithmica 82, No. 12, 3492--3520 (2020; Zbl 1494.68202) Full Text: DOI arXiv
Matl, Gregor; Živný, Stanislav Beyond Boolean surjective VCSPs. (English) Zbl 07559161 Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 52, 15 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{G. Matl} and \textit{S. Živný}, LIPIcs -- Leibniz Int. Proc. Inform. 126, Article 52, 15 p. (2019; Zbl 07559161) Full Text: DOI
Cohen, David A.; Cooper, Martin C.; Jeavons, Peter G.; Živný, Stanislav Binary constraint satisfaction problems defined by excluded topological minors. (English) Zbl 1408.68130 Inf. Comput. 264, 12-31 (2019). MSC: 68T20 05C83 68Q25 PDFBibTeX XMLCite \textit{D. A. Cohen} et al., Inf. Comput. 264, 12--31 (2019; Zbl 1408.68130) Full Text: DOI arXiv Link
Koponen, Vera On constraints and dividing in ternary homogeneous structures. (English) Zbl 1477.03142 J. Symb. Log. 83, No. 4, 1691-1721 (2018). MSC: 03C50 03C10 03C45 03C13 03C15 03C30 PDFBibTeX XMLCite \textit{V. Koponen}, J. Symb. Log. 83, No. 4, 1691--1721 (2018; Zbl 1477.03142) Full Text: DOI arXiv
Siggers, Mark Reflexive graphs with near unanimity but no semilattice polymorphisms. (English) Zbl 1401.05253 Electron. J. Comb. 25, No. 4, Research Paper P4.2, 13 p. (2018). MSC: 05C75 08B05 06A07 PDFBibTeX XMLCite \textit{M. Siggers}, Electron. J. Comb. 25, No. 4, Research Paper P4.2, 13 p. (2018; Zbl 1401.05253) Full Text: Link
Brewster, Richard C.; Siggers, Mark A complexity dichotomy for signed \(\mathbf{H}\)-colouring. (English) Zbl 1393.05108 Discrete Math. 341, No. 10, 2768-2773 (2018). MSC: 05C15 05C22 PDFBibTeX XMLCite \textit{R. C. Brewster} and \textit{M. Siggers}, Discrete Math. 341, No. 10, 2768--2773 (2018; Zbl 1393.05108) Full Text: DOI
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
Gaspers, Serge; Ordyniak, Sebastian; Szeider, Stefan Backdoor sets for CSP. (English) Zbl 1482.68163 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, 137-157 (2017). MSC: 68R07 08A70 68Q25 68Q27 PDFBibTeX XMLCite \textit{S. Gaspers} et al., Dagstuhl Follow-Ups 7, 137--157 (2017; Zbl 1482.68163) Full Text: DOI
Cooper, Martin C.; Zivny, Stanislav Hybrid tractable classes of constraint problems. (English) Zbl 1482.68107 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, 113-135 (2017). MSC: 68Q25 68R05 90C27 PDFBibTeX XMLCite \textit{M. C. Cooper} and \textit{S. Zivny}, Dagstuhl Follow-Ups 7, 113--135 (2017; Zbl 1482.68107) Full Text: DOI
Koponen, Vera Homogeneous 1-based structures and interpretability in random structures. (English) Zbl 1469.03089 Math. Log. Q. 63, No. 1-2, 6-18 (2017). MSC: 03C13 60C05 03C45 PDFBibTeX XMLCite \textit{V. Koponen}, Math. Log. Q. 63, No. 1--2, 6--18 (2017; Zbl 1469.03089) Full Text: DOI arXiv
Fulla, Peter; Živný, Stanislav On planar valued CSPs. (English) Zbl 1370.68125 J. Comput. Syst. Sci. 87, 104-118 (2017). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{P. Fulla} and \textit{S. Živný}, J. Comput. Syst. Sci. 87, 104--118 (2017; Zbl 1370.68125) Full Text: DOI arXiv
Carbonnel, Clément; Cooper, Martin C. Tractability in constraint satisfaction problems: a survey. (English) Zbl 1334.90220 Constraints 21, No. 2, 115-144 (2016). MSC: 90C60 90C30 PDFBibTeX XMLCite \textit{C. Carbonnel} and \textit{M. C. Cooper}, Constraints 21, No. 2, 115--144 (2016; Zbl 1334.90220) Full Text: DOI Link
Jonsson, Peter; Thapper, Johan Constraint satisfaction and semilinear expansions of addition over the rationals and the reals. (English) Zbl 1338.68108 J. Comput. Syst. Sci. 82, No. 5, 912-928 (2016). MSC: 68Q25 90C05 PDFBibTeX XMLCite \textit{P. Jonsson} and \textit{J. Thapper}, J. Comput. Syst. Sci. 82, No. 5, 912--928 (2016; Zbl 1338.68108) Full Text: DOI arXiv
Koponen, Vera Binary simple homogeneous structures are supersimple with finite rank. (English) Zbl 1352.03044 Proc. Am. Math. Soc. 144, No. 4, 1745-1759 (2016). Reviewer: Isaac Goldbring (Irvine) MSC: 03C10 03C45 03C50 03C52 03C68 PDFBibTeX XMLCite \textit{V. Koponen}, Proc. Am. Math. Soc. 144, No. 4, 1745--1759 (2016; Zbl 1352.03044) Full Text: DOI arXiv
Kun, Gábor; Szegedy, Mario A new line of attack on the dichotomy conjecture. (English) Zbl 1327.05183 Eur. J. Comb. 52, Part B, 338-367 (2016). MSC: 05C40 68Q17 PDFBibTeX XMLCite \textit{G. Kun} and \textit{M. Szegedy}, Eur. J. Comb. 52, Part B, 338--367 (2016; Zbl 1327.05183) Full Text: DOI
Thapper, Johan; Živný, Stanislav Necessary conditions for tractability of valued CSPs. (English) Zbl 1347.08009 SIAM J. Discrete Math. 29, No. 4, 2361-2384 (2015). MSC: 08A70 68Q25 68Q17 PDFBibTeX XMLCite \textit{J. Thapper} and \textit{S. Živný}, SIAM J. Discrete Math. 29, No. 4, 2361--2384 (2015; Zbl 1347.08009) Full Text: DOI arXiv
Fulla, Peter; Živný, Stanislav A Galois connection for valued constraint languages of infinite size. (English) Zbl 1440.68115 Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 517-528 (2015). MSC: 68Q25 06A15 08A40 08A70 PDFBibTeX XMLCite \textit{P. Fulla} and \textit{S. Živný}, Lect. Notes Comput. Sci. 9134, 517--528 (2015; Zbl 1440.68115) Full Text: DOI
Kolmogorov, Vladimir; Thapper, Johan; Živný, Stanislav The power of linear programming for general-valued CSPs. (English) Zbl 1456.68059 SIAM J. Comput. 44, No. 1, 1-36 (2015). MSC: 68Q25 68Q17 68R07 90C05 90C27 PDFBibTeX XMLCite \textit{V. Kolmogorov} et al., SIAM J. Comput. 44, No. 1, 1--36 (2015; Zbl 1456.68059) Full Text: DOI arXiv
Hell, Pavol; Mishra, Aurosish \(H\)-coloring degree-bounded (acyclic) digraphs. (English) Zbl 1382.68112 Theor. Comput. Sci. 554, 40-49 (2014). MSC: 68Q25 05C15 05C20 05C85 68Q17 PDFBibTeX XMLCite \textit{P. Hell} and \textit{A. Mishra}, Theor. Comput. Sci. 554, 40--49 (2014; Zbl 1382.68112) Full Text: DOI
Hell, Pavol; Pultr, Aleš Connected obstructions to full graph homomorphisms. (English) Zbl 1300.05181 Eur. J. Comb. 41, 278-288 (2014). MSC: 05C60 PDFBibTeX XMLCite \textit{P. Hell} and \textit{A. Pultr}, Eur. J. Comb. 41, 278--288 (2014; Zbl 1300.05181) Full Text: DOI
Hell, Pavol Graph partitions with prescribed patterns. (English) Zbl 1292.05214 Eur. J. Comb. 35, 335-353 (2014). MSC: 05C70 05C69 05C15 05C50 PDFBibTeX XMLCite \textit{P. Hell}, Eur. J. Comb. 35, 335--353 (2014; Zbl 1292.05214) Full Text: DOI
Feder, Tomás; Hell, Pavol; Nekooei Rizi, Shekoofeh Obstructions to partitions of chordal graphs. (English) Zbl 1277.05137 Discrete Math. 313, No. 19, 1861-1871 (2013). MSC: 05C70 05C60 05C17 68Q17 68Q25 PDFBibTeX XMLCite \textit{T. Feder} et al., Discrete Math. 313, No. 19, 1861--1871 (2013; Zbl 1277.05137) Full Text: DOI
Kolmogorov, Vladimir; Živný, Stanislav The complexity of conservative valued CSPs. (English) Zbl 1423.68215 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 750-759 (2012). MSC: 68Q25 90C27 PDFBibTeX XMLCite \textit{V. Kolmogorov} and \textit{S. Živný}, in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 750--759 (2012; Zbl 1423.68215) Full Text: Link
MacGillivray, Gary; Swarts, Jacobus The \(C_{k}\)-extended graft construction. (English) Zbl 1223.05300 Discrete Appl. Math. 159, No. 12, 1293-1301 (2011). MSC: 05C85 05C20 05C30 05C31 PDFBibTeX XMLCite \textit{G. MacGillivray} and \textit{J. Swarts}, Discrete Appl. Math. 159, No. 12, 1293--1301 (2011; Zbl 1223.05300) Full Text: DOI
Nešetřil, Jaroslav; Siggers, Mark H.; Zádori, László A combinatorial constraint satisfaction problem dichotomy classification conjecture. (English) Zbl 1187.68250 Eur. J. Comb. 31, No. 1, 280-296 (2010). MSC: 68Q17 90C27 PDFBibTeX XMLCite \textit{J. Nešetřil} et al., Eur. J. Comb. 31, No. 1, 280--296 (2010; Zbl 1187.68250) Full Text: DOI
Ball, Richard N.; Nešetřil, Jaroslav; Pultr, Aleš Dualities in full homomorphisms. (English) Zbl 1219.05092 Eur. J. Comb. 31, No. 1, 106-119 (2010). MSC: 05C60 PDFBibTeX XMLCite \textit{R. N. Ball} et al., Eur. J. Comb. 31, No. 1, 106--119 (2010; Zbl 1219.05092) Full Text: DOI