Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Professor
Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Professor
B. Larose
H. Alt
Editor
M. Habib
Editor
We combine methods of order theory, finite model theory, and universal algebra to study, within the constraint satisfaction framework, the complexity of some well-known combinatorial problems connected with a finite poset. We identify some conditions on a poset which guarantee solvability of the problems in (deterministic, symmetric, or non-deterministic) logarithmic space. On the example of order constraints we study how a certain algebraic invariance property is related to solvability of a constraint satisfaction problem in non-deterministic logarithmic space.
Krokhin, A., & Larose, B. (2003). Solving order constraints in logarithmic space. In H. Alt, & M. Habib (Eds.), 20th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2003, 27 February-1 March 1 2003 ; proceedings (379-390). https://doi.org/10.1007/3-540-36494-3_34
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science {(STACS'03) Berlin |
Publication Date | Mar 1, 2003 |
Deposit Date | Mar 29, 2010 |
Publicly Available Date | Apr 6, 2010 |
Publisher | Springer Verlag |
Pages | 379-390 |
Series Title | Lecture notes in computer science |
Series Number | 2607 |
Book Title | 20th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2003, 27 February-1 March 1 2003 ; proceedings. |
ISBN | 9783540006237 |
DOI | https://doi.org/10.1007/3-540-36494-3_34 |
Public URL | https://durham-repository.worktribe.com/output/1162345 |
Accepted Conference Proceeding
(230 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/3-540-36494-3_34
Algebraic approach to promise constraint satisfaction
(2019)
Presentation / Conference Contribution
The complexity of 3-colouring H-colourable graphs
(2020)
Presentation / Conference Contribution
Robust algorithms with polynomial loss for near-unanimity CSPs
(2017)
Presentation / Conference Contribution
The Complexity of General-Valued CSPs
(2015)
Presentation / Conference Contribution
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search