Structural properties of graphs with no long paths
Public support
Provider
Ministry of Education, Youth and Sports
Programme
Promoting the mobility of researchers and workers in the framework of international cooperation in R&D
Call for proposals
—
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
M2 - International cooperation
Contract ID
27731/2018-2
Alternative language
Project name in Czech
Strukturální vlastnosti grafů bez dlouhých ces
Annotation in Czech
Dědičné třídy grafů, tj. třídy uzavřené na odebírání vrcholů jsou důležité a intenzivně studované třídy grafů. V rámci projektu plánujeme studovat algoritmické a strukturální aspekty dědičných tříd a obzvlášť se plánujeme zaměřit na třídy bez dlouhých indukovaných cest. Prvním cílem projektu je výzkum efektivních algoritmů pro grafy bez dlouhých cest pro problémy, které jsou obecně NP-těžké. Konkrétně se chceme zaměřit na problém feedback vrcholové množiny, to jest, nejmenší množiny vrcholů jejíž odebráním vznikne les, pro P_5-free grafy. To by rozšířilo výsledek francouzské řešitelky. Naším druhým cílem je strukturální aspekt dědičných tříd grafů, konkrétně hledání charakterizace dědičné třídy definované grafovým parametrem pomocí minimálního počtu zakázaných indukovaných podgrafů. Konkrétně se chceme zaměřit na třídy s omezenou cenou souvislosti nějakého grafového parametru, to jest poměru mezi grafovým parametrem a souvislou verzí daného parametru (například mezi velikostí nejmenší dominující množiny a nejmenší souvislé dominující množiny).
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10101 - Pure mathematics
OECD FORD - secondary branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - another secondary branch
—
CEP - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
AF - Documentation, librarianship, work with information<br>BA - General mathematics<br>BC - Theory and management systems<br>BD - Information theory<br>IN - Informatics
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
This project was being realized in the framework of the MOBILITY Activity that aims primarily on establishing and strenghtening ties with foreign research institutions. The control of particular outputs is not implemented by the evalution committee, but the correctness of allocated finances and the adequacy of their use are checked.
Solution timeline
Realization period - beginning
Jan 1, 2019
Realization period - end
Dec 31, 2021
Project status
U - Finished project
Latest support payment
Apr 29, 2020
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
CEP22-MSM-8J-U
Data delivery date
Jun 30, 2022
Finance
Total approved costs
96 thou. CZK
Public financial support
96 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK