Strukturální vlastnosti grafů bez dlouhých ces

Poskytovatel

Ministerstvo školství, mládeže a tělovýchovy

Program

Podpora mobility výzkumných pracovníků a pracovnic v rámci mezinárodní spolupráce ve VaVaI

Veřejná soutěž

—

Hlavní účastníci

Univerzita Karlova / Matematicko-fyzikální fakulta

Druh soutěže

M2 - Mezinárodní spolupráce

Číslo smlouvy

27731/2018-2

Název projektu anglicky

Structural properties of graphs with no long paths

Anotace anglicky

Hereditary graph classes, that is, classes closed under vertex deletion, are an important type graph classes which is intensively studied. In the project, we intend to study structural and algorithmic and structural aspects of hereditary graph classes, with a particular focus on classes without long induced paths. First aim of the project is developing efficient algorithms on graphs with no long paths for problems, which are NP-hard in general. Specifically, we want to focus on the problem of Feedback vertex set, that is, detecting a set whose removal yields a forest, for P_5-free graphs, extending a result of French PI. Our second objective targets the structural aspect of hereditary graph classes, seeking a minimal characterisation of a hereditary graph class defined through some graph parameters. In particular, we would like to focus on classes with bounded price of connectivity for some graph parameter, that is, a ratio between a graph parameter and connected version of the graph parameter (for instance between the minimum size of dominating set and the minimum size of connected dominating set).

Kategorie VaV

ZV - Základní výzkum

OECD FORD - hlavní obor

10101 - Pure mathematics

OECD FORD - vedlejší obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

OECD FORD - další vedlejší obor

—

CEP - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

AF - Dokumentace, knihovnictví, práce s informacemi<br>BA - Obecná matematika<br>BC - Teorie a systémy řízení<br>BD - Teorie informace<br>IN - Informatika

Hodnocení poskytovatelem

U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)

Zhodnocení výsledků projektu

Projekt byl realizován v rámci Aktivity MOBILITY, jejímž hlavním cílem je navázání a prohlubování kontaktů se zahraničními výzkumnými institucemi. Neprobíhá tedy kontrola dílčích výstupů projektu prostřednictvím hodnotící komise, avšak je kontrolována správnost čerpání přidělených financí a přiměřenost jejich využití.

Zahájení řešení

1. 1. 2019

Ukončení řešení

31. 12. 2021

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

29. 4. 2020

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

CEP22-MSM-8J-U

Datum dodání záznamu

30. 6. 2022

Celkové uznané náklady

96 tis. Kč

Výše podpory ze státního rozpočtu

96 tis. Kč

Ostatní veřejné zdroje financování

0 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč