Colourings, cycles and closures
Public support
Provider
Ministry of Education, Youth and Sports
Programme
KONTAKT
Call for proposals
—
Main participants
—
Contest type
M2 - International cooperation
Contract ID
8038/2010-32
Alternative language
Project name in Czech
Barevnost, cykly a uzávěry
Annotation in Czech
Předložený projekt spadá do oblasti základního výzkumu v diskrétní matematice ? teoretické informatice. Plánovaný výzkum se koncentruje do dvou základních oblastí ? problematika duhových podgrafů a problematika ?dlouhých? kružnic v neorientovaných grafech. Oba problémy náleží ke klasickým algoritmicky velmi obtížným (NP-těžkým) problémům, a pro jejich řešení nejsou známy žádné efektivní ( = pracující v polynomiálním čase) algoritmy. Pro oba problémy jsou však známy výsledky, které ukazují, že při vhodnérestrikci vstupní instance (tj. v některých speciálních třídách grafů) mohou tyto problémy být (s použitím speciálních technik) řešitelné v polynomiálním čase, či alespoň polynomiálně aproximovatelné. Plánovaný výzkum bude orientován právě do této oblasti, přičemž pozornost bude věnována zejména (ale nikoliv výhradně) grafům z některých dědičných tříd, charakterizovaných pomocí zakázaných indukovaných podgrafů. Oba týmy patří v daných oblastech k předním pracovištím a propojením vzniknou podmínky pro
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BA - General mathematics
CEP - secondary branch
—
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
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
During reciprocal working visits, organized within the project, two joint scientific publications have been completed.
Solution timeline
Realization period - beginning
Jan 1, 2010
Realization period - end
Dec 31, 2011
Project status
U - Finished project
Latest support payment
Mar 7, 2011
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
CEP12-MSM-ME-U/01:1
Data delivery date
Jul 12, 2012
Finance
Total approved costs
90 thou. CZK
Public financial support
90 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK