Algebraický přístup k CSP
| Thesis title in Czech: | Algebraický přístup k CSP |
|---|---|
| Thesis title in English: | The Algebraic Approach to CSP |
| Key words: | problém splňování omezení, barvení grafů, konečná šířka, speciální triáda |
| English key words: | constraint satisfaction problem, graph coloring, bounded width, special triad |
| Academic year of topic announcement: | 2008/2009 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | doc. Mgr. Libor Barto, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 11.11.2008 |
| Date of assignment: | 11.11.2008 |
| Date and time of defence: | 16.09.2010 00:00 |
| Date of electronic submission: | 16.09.2010 |
| Date of proceeded defence: | 16.09.2010 |
| Opponents: | doc. Mgr. Pavel Růžička, Ph.D. |
| Guidelines |
| Práce se bude zabývat algebraickým přístupem k problému CSP (Constraint Satisfaction Problem). Lze se zaměřit na studium některých speciálních struktur (různé druhy orientovaných stromů a jiných grafů), rozpracování relevantních algebraických nástrojů, zjednodušení důkazů známých vět algebraickými metodami, apod. |
| References |
| [1] L. Barto, M. Kozik, M. Maroti, R. McKenzie, T. Niven, Congruence modularity implies cyclic terms for finite algebras, to appear in Alebra Universalis
[2] L. Barto, M. Kozik, M. Maroti, T. Niven, CSP dichotomy for special triads, manuscript [3] L. Barto, M. Kozik, T. Niven, Graphs, Polymorphisms and the Complexity of Homomorphism Problems, Proceedings of the 40th ACM Symposium on Theory of Computing, STOC'08 (2008), 789-796 [4] T. Feder, Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability, SIAM Journal on Discrete Mathematics 14/4 (2001), 471 - 480 [5] D. Hobby, R. McKenzie, The structure of finite algebras, AMS Contemporary Mathematics vol. 76, revised edition (1991). |
| Preliminary scope of work |
| Práce se bude zabývat algebraickým přístupem k problému CSP (Constraint Satisfaction Problem). Lze se zaměřit na studium některých speciálních struktur (různé druhy orientovaných stromů a jiných grafů), rozpracování relevantních algebraických nástrojů, zjednodušení důkazů známých vět algebraickými metodami, apod. |
| Preliminary scope of work in English |
| The thesis will be devoted to the algebraic approach to the CSP (Constraint Satisfaction Problem). The student may study selected special structures (various kinds of oriented trees, or other types of graphs), develop new algebraic tools, simplify proofs of known results by the algebraic methods, etc. |