| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Andrei A. Krokhin, Dániel Marx |
On the hardness of losing weight.  |
ACM Transactions on Algorithms  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | László Egri, Andrei A. Krokhin, Benoit Larose, Pascal Tesson |
The Complexity of the List Homomorphism Problem for Graphs. |
Theory Comput. Syst. |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin |
Two new homomorphism dualities and lattice operations. |
J. Log. Comput. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin |
A Maximal Tractable Class of Soft Constraints |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Andrei A. Krokhin |
The Complexity of Evaluating First-Order Sentences over a Fixed Structure. |
LICS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin |
CSP duality and trees of bounded pathwidth. |
Theor. Comput. Sci. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Tomás Feder, Pavol Hell, Peter Jonsson, Andrei A. Krokhin, Gustav Nordh |
Retractions to Pseudoforests. |
SIAM J. Discrete Math. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | László Egri, Andrei A. Krokhin, Benoit Larose, Pascal Tesson |
The Complexity of the List Homomorphism Problem for Graphs. |
STACS |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Krokhin |
Tree Dualities for Constraint Satisfaction. |
CSL |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen |
Hard constraint satisfaction problems have hard gaps at location 1. |
Theor. Comput. Sci. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, Andrei A. Krokhin |
The complexity of constraint satisfaction games and QCSP. |
Inf. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | László Egri, Andrei A. Krokhin, Benoit Larose, Pascal Tesson |
The complexity of the list homomorphism problem for graphs |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Víctor Dalmau, Andrei A. Krokhin, Benoit Larose |
Retractions onto series-parallel posets. |
Discrete Mathematics |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Víctor Dalmau, Andrei A. Krokhin |
Majority constraints have bounded pathwidth duality. |
Eur. J. Comb. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin |
The approximability of MAX CSP with fixed-value constraints. |
J. ACM |
2008 |
DBLP DOI BibTeX RDF |
Complexity of approximation, maximum constraint satisfaction, dichotomy, Monge properties, supermodularity |
| 1 | Andrei A. Krokhin, Benoit Larose |
Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction. |
SIAM J. Discrete Math. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Nadia Creignou, Miki Hermann, Andrei A. Krokhin, Gernot Salzer |
Complexity of Clausal Constraints Over Chains. |
Theory Comput. Syst. |
2008 |
DBLP DOI BibTeX RDF |
Finite totally ordered domains, Clausal patterns, Dichotomy theorem, Complexity, Constraint satisfaction problems, Inequalities |
| 1 | Peter Jonsson, Andrei A. Krokhin |
Computational complexity of auditing finite attributes in statistical databases. |
J. Comput. Syst. Sci. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Dániel Marx |
On the Hardness of Losing Weight. |
ICALP |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Bulatov, Andrei A. Krokhin, Benoit Larose |
Dualities for Constraint Satisfaction Problems. |
Complexity of Constraints |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin |
Caterpillar Duality for Constraint Satisfaction Problems. |
LICS |
2008 |
DBLP DOI BibTeX RDF |
caterpillar structures, Datalog, duality, constraint satisfaction problem, homomorphism |
| 1 | Víctor Dalmau, Andrei A. Krokhin, Benoit Larose |
First-order Definable Retraction Problems for Posets and Reflexive Graphs. |
J. Log. Comput. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen |
Hard constraint satisfaction problems have hard gaps at location 1 |
CoRR |
2007 |
DBLP BibTeX RDF |
|
| 1 | Peter Jonsson, Andrei A. Krokhin |
Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. |
J. Comput. Syst. Sci. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen |
Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. |
CSR |
2007 |
DBLP DOI BibTeX RDF |
maximum constraint satisfaction, complexity, approximability |
| 1 | Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin |
The approximability of MAX CSP with fixed-value constraints |
CoRR |
2006 |
DBLP BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Ivo G. Rosenberg |
A Monoidal Interval of Clones of Selfdual Functions. |
Journal of Automata, Languages and Combinatorics |
2006 |
DBLP BibTeX RDF |
|
| 1 | David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin |
The complexity of soft constraint satisfaction. |
Artif. Intell. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Jonsson, Mikael Klasson, Andrei A. Krokhin |
The Approximability of Three-valued MAX CSP. |
SIAM J. Comput. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin |
Supermodular functions and the complexity of MAX CSP. |
Discrete Applied Mathematics |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin |
Classifying the Complexity of Constraints Using Finite Algebras. |
SIAM J. Comput. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Benoit Larose |
Maximum Constraint Satisfaction on Diamonds. |
CP |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Jonsson, Andrei A. Krokhin |
Recognizing frozen variables in constraint satisfaction problems. |
Theor. Comput. Sci. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Jonsson, Mikael Klasson, Andrei A. Krokhin |
The approximability of three-valued MAX CSP |
CoRR |
2004 |
DBLP BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Peter Jeavons, Peter Jonsson |
Constraint Satisfaction Problems on Intervals and Length. |
SIAM J. Discrete Math. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin |
A Maximal Tractable Class of Soft Constraints. |
J. Artif. Intell. Res. (JAIR) |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Jonsson, Andrei A. Krokhin |
Complexity classification in qualitative temporal constraint reasoning. |
Artif. Intell. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin |
Identifying Efficiently Solvable Cases of Max CSP. |
STACS |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Víctor Dalmau, Andrei A. Krokhin, Benoit Larose |
First-Order Definable Retraction Problems for Posets and Reflexive Graph. |
LICS |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Peter Jonsson |
Recognizing Frozen Variables in Constraint Satisfaction Problems |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Peter Jeavons, Peter Jonsson |
Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. |
J. ACM |
2003 |
DBLP DOI BibTeX RDF |
Allen's algebra, dichotomy theorem, representing graphs by intervals, satisfiability of temporal constraints, tractable cases, complexity, NP-completeness |
| 1 | David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin |
A Maximal Tractable Class of Soft Constraints. |
IJCAI |
2003 |
DBLP BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Benoit Larose |
Solving Order Constraints in Logarithmic Space. |
STACS |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Andrei A. Bulatov, Peter Jeavons |
Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. (PDF / PS) |
ISMVL |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Ferdinand Börner, Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin |
Quantified Constraints: Algorithms and Complexity. |
CSL |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin |
Soft Constraints: Complexity and Multimorphisms. |
CP |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Peter Jonsson |
Extending the Point Algebra into the Qualitative Algebra. (PDF / PS) |
TIME |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Peter Jeavons, Peter Jonsson |
The Complexity of Constraints on Intervals and Lengths. |
STACS |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Peter Jeavons, Peter Jonsson |
The complexity of constraints on intervals and lengths |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Andrei A. Krokhin |
Congruences of Clone Lattices, II. |
Order |
2001 |
DBLP DOI BibTeX RDF |
clone lattice, clone, congruence |
| 1 | Andrei A. Krokhin, Peter Jeavons, Peter Jonsson |
A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation. |
IJCAI |
2001 |
DBLP BibTeX RDF |
|
| 1 | Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons |
The complexity of maximal constraint languages. |
STOC |
2001 |
DBLP DOI BibTeX RDF |
algebraic invariance property, constraint satisfaciton problem, relational clone, complexity, NP-completeness, tractability, constraint language |
| 1 | Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons |
Constraint Satisfaction Problems and Finite Algebras. |
ICALP |
2000 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")