Barevnost, cykly a uzávěry

Název projektu anglicky
Colourings, cycles and closures
Anotace anglicky
In this joint project we will consider two important problems in the field of Graph Theory. The first problem asks for the computation of a minimum rainbow subgraph (MRS) of a given graph G; The second problem asks for the computation of a longest cyclein a given (finite) graph. Both problems are well-known NP-hard and NP-complete problems, respectively. Hence no efficient algorithms are known for solving them exactly. However, if we restrict the input class of graphs, these problems eventually becomealgorithmically efficiently solvable or approximable. The MRS problem is known to be approximable in polynomial time with an approximation ratio of 5/3 for the class of graphs with maximum degree two. The planned research is a continuation of the previous cooperation of both principal investigators (15 joint papers). The project also aims to further extend this previous successful cooperation and to extend it by involving young researchers and graduate students at both institutions.

Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
—
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)
10101 - Pure mathematics

Hodnocení poskytovatelem
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Zhodnocení výsledků projektu
Byly realizovány reciproční pracovní návštěvy, při nichž byly dokončeny dvě společné vědecké publikace.

Důvěrnost údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Systémové označení dodávky dat
CEP12-MSM-ME-U/01:1
Datum dodání záznamu
12. 7. 2012

Podobné projekty(10)