An Algebraic Approach to the Constraint Satisfaction Problem
Public support
Provider
Ministry of Education, Youth and Sports
Programme
KONTAKT
Call for proposals
—
Main participants
—
Contest type
M2 - International cooperation
Contract ID
1484/2009-32
Alternative language
Project name in Czech
Algebraický přístup k problému splnitelnosti omezujících podmínek
Annotation in Czech
Hlavním cílem spolupráce je umožnit českým a polským řešitelům sdílet zkušenosti a myšlenky týkající se problému splnitelnosti omezujících podmínek (CSP), zejména otázky dichotomie. Spolupráce již započala četnými návštěvami polských účastníků v České Republice, které vedly k významným příspěvkům v dané oblasti. Spolupráce se zaměří na algebraický přístup k problému CSP, který se ukázal být velmi plodným. V průběhu řešení chceme rozšířit třídu problémů, pro které je dichotomie známa, zejména se zaměřímena třídy orientovaných grafů. To povede k rozvoji teorie nutné k důkazu (nebo vyvrácení) dichotomické domněky. Prvním krokem je aplikovat algebraické nástroje pro třídy, pro něž je dichotomie známa: orientované cesty, orientované kružnice, turnaje a mnoho dalších. Tento výzkum poskytne východisko k důkazu dichotomie pro širší třídu digrafů a jiných relačních struktur. Velmi důležité je uzpůsobit algebraické nástroje, které se již ukázali být velmi užitečné. Zkoumání malcevských podmínek ve s
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BA - General mathematics
CEP - secondary branch
IN - Informatics
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
10101 - Pure mathematics<br>10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The results of this project include the solution of the Larose-Zádori bounded width conjecture and a proof of the strongest criterion fo NP-completenenss known so far. The results were accepted in top journals and presented at first-rate conferences.
Solution timeline
Realization period - beginning
Jan 1, 2008
Realization period - end
Dec 31, 2009
Project status
U - Finished project
Latest support payment
Mar 9, 2009
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP10-MSM-ME-U/01:1
Data delivery date
Jun 30, 2010
Finance
Total approved costs
90 thou. CZK
Public financial support
85 thou. CZK
Other public sources
5 thou. CZK
Non public and foreign sources
0 thou. CZK