Informační systém výzkumu,
vývoje a inovací

Centrální evidence projektů

Jednoduché vyhledávání

Zpět na hledáníGA201/05/0050 - Strukturální vlastnosti a algoritmická složitost diskrétních problémů (2005-2007, GA0/GA)

Identifikační kód GA201/05/0050
Důvěrnost údajů S - Není předmětem státního či obchodního tajemství a data lze v souladu s právními předpisy poskytnout do veřejně přístupných informačních systémů včetně mezinárodních
Název projektu v původním jazyce Strukturální vlastnosti a algoritmická složitost diskrétních problémů
Název projektu anglicky Structural properties and algorithmic complexity of discrete problems
Poskytovatel GA0 - Grantová agentura České republiky (GA ČR)
Program GA - Standardní projekty  (1993 - 2050)
Kategorie VaV ZV - Základní výzkum
Hlavní obor - skupina B - Fyzika a matematika
Hlavní obor BA - Obecná matematika
Vedlejší obor IN - Informatika
Další vedlejší obor -
Zahájení řešení 01.01.2005
Ukončení řešení 31.12.2007
Datum posledního uvolnění účelové podpory 02.05.2007
Číslo smlouvy 201/05/0050
Poslední stav řešení U - Ukončený (rok ukončení projektu < rok sběru dat, v roce sběru dat již není financován ze SR)
Kčtis. Kč **
Finance projektu		200520062007celkem
Výše podpory z národních zdrojů147 000,00147148 000,00148158 000,00158453 000,00453
Výše podpory z veřej. zahraničních zdrojů ***0,0000,0000,0000,000
Neveřejné tuzem. a zahr. zdroje financování---28 000,0028
Celkové uznané náklady156 000,00156148 000,00148168 000,00168472 000,00472
Typčerpanéčerpanéčerpané

** Finance v tisících Kč jsou automaticky zaokrouhleny z částky v jednotkách Kč s přesností na 2 desetinná místa
*** Výše podpory z veřejných zahraničních zdrojů je sledována od období sběru 2020

Zobrazit skutečně čerpané finance projektu z národních zdrojů »
Druh soutěže VS - Veřejná soutěž
Veřejná soutěž ve výzkumu, vývoji a inovacích SGA02005GA-ST - Veřejná soutěž (GA0/GA)
Cíle řešení v původním jazyce V pozadí mnoha praktických algoritmických problémů stojí struktury diskrétní matematiky, jako je graf nebo obecněji matroid. Jak se však ukazuje, většina již základních diskrétních problémů je "téměř neřešitelná" (NP-těžká) ve své obecné formulaci. Přesto je žádoucí hledat alespoň přibližná řešení takových těžkých problémů, nebo řešení fungující za dodatečných předpokladů. Klíčem k nalezení vhodných předpokladů umožňujících efektivní řešení těžkých problémů přitom je pochopení jejich vnitřní struktury.Jako příklad úspěchu tohoto strukturálního přístupu bychom zmínili hlubokou a převratnou teorii grafových minorů Robertsona a Seymoura. Mimo to je zde nová teorie parametrizované složitosti algoritmů Downeyho a Fellowse. Náplní našeho projektuje rozvíjení strukturálních přístupů k těžkým diskrétním problémům, zvláště s důrazem na stromovou či větvenou šířku grafů a matroidů. To zahrnuje nové aplikace strukturálních metod při vývoji parametrizovaně efektivních algoritmů na grafech, například
Cíle řešení v anglickém jazyce Many practical algorithmic problems have a core based on the structures of discrete mathematics, like on graphs or matroids. It turns out that majority of the basic discrete problems are "almost unsolvable" (NP-hard) in their general formulation. Still,one has to look for, at least, approximate solutions to hard problems, or at solutions working under additional assumptions. The key to finding suitable assumptions allowing for effective solutions of hard problems lies in understanding their structure.As an example of a great success of structural approaches, we mention the deep and revolutionary Graph Minor Theory of Robertson and Seymour. Moreover, there is the new theory of parametrized complexity of algorithms by Downey and Fellows. The topic of our project is development of structural approaches to hard discrete problems, especially with emphasis on tree- or branch-width of graphs and matroids. Those include new applications of the structural methods in design of fixed parameter tractable
Klíčová slova v anglickém jazyce graph; matroid; tree-width; clique-width; graph minors; crossing number; parametrized complexity
Kontrolní číslo stavu projektu v letech 2005: 1542481
2006: 33504994
2007: 2167311
2008: 167280942
Datum dodání posledního záznamu o projektu 16.12.2008
Systémové označení dodávky dat CEP08-GA0-GA-U/04:3

Účastníci projektu

Počet příjemců 0
Počet dalších účastníků projektu 1
Další účastník projektu Vysoká škola báňská - Technická univerzita Ostrava / Fakulta elektrotechniky a informatiky

Kčtis. Kč **
Finance účastníků projektuPoznámka: Finance účastníků projektu jsou sledovány od roku 2007, investiční prostředky od roku 2013, prostředky ze zahraničních zdrojů od roku 2020

Celkové uznané náklady200520062007
Vysoká škola báňská - Technická univerzita Ostrava / Fakulta elektrotechniky a informatiky0,0000,000168 000,00168
Výše podpory z národních zdrojů200520062007
Vysoká škola báňská - Technická univerzita Ostrava / Fakulta elektrotechniky a informatiky0,0000,000158 000,00158
Výše podpory z veřejných zahraničních zdrojů200520062007
Vysoká škola báňská - Technická univerzita Ostrava / Fakulta elektrotechniky a informatiky0,0000,0000,000
Investiční prostředky z podpory ze státního rozpočtu na účastníka v daném roce200520062007
Vysoká škola báňská - Technická univerzita Ostrava / Fakulta elektrotechniky a informatiky0,0000,0000,000

** Finance v tisících Kč jsou automaticky zaokrouhleny z částky v jednotkách Kč s přesností na 2 desetinná místa

Zobrazit skutečně čerpané prostředky z národních zdrojů na účastníka »

Výsledky projektu v RIV

Počet výsledků projektu v RIV celkem 67
Výsledek druhu A RIV/00216224:14330/05:00012608 - MACEK: A software package for real structural computations with representable matroids (2005)
Výsledek druhu A RIV/00216224:14330/05:00012608 - MACEK: A software package for real structural computations with representable matroids (2005)
Výsledek druhu A RIV/00216224:14330/05:00012608 - MACEK: A software package for real structural computations with representable matroids (2005)
Výsledek druhu J RIV/00216224:14330/05:00012661 - Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (2005)
Výsledek druhu J RIV/00216224:14330/05:00012661 - Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (extended abstract) (2005)
Výsledek druhu D RIV/00216224:14330/05:00012661 - Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (extended abstract) (2005)
Výsledek druhu J RIV/00216224:14330/05:00012752 - A Parametrized Algorithm for Matroid Branch-Width (2005)
Výsledek druhu J RIV/00216224:14330/05:00012752 - A Parametrized Algorithm for Matroid Branch-Width (2005)
Výsledek druhu J RIV/00216224:14330/05:00012752 - A Parametrized Algorithm for Matroid Branch-Width (2005)
Výsledek druhu J RIV/00216224:14330/05:00028918 - Bridging Separations in Matroids (2005)
Výsledek druhu J RIV/00216224:14330/06:00015568 - Crossing Number is Hard for Cubic Graphs (2006)
Výsledek druhu J RIV/00216224:14330/06:00015568 - Crossing Number is Hard for Cubic Graphs (2006)
Výsledek druhu J RIV/00216224:14330/06:00015568 - Crossing Number is Hard for Cubic Graphs (2006)
Výsledek druhu J RIV/00216224:14330/06:00015569 - Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids (2006)
Výsledek druhu J RIV/00216224:14330/06:00015569 - Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids (2006)
Výsledek druhu J RIV/00216224:14330/06:00015569 - Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids (2006)
Výsledek druhu J RIV/00216224:14330/06:00015570 - Trees, grids, and MSO decidability: From graphs to matroids (2006)
Výsledek druhu J RIV/00216224:14330/06:00015570 - Trees, grids, and MSO decidability: From graphs to matroids (2006)
Výsledek druhu J RIV/00216224:14330/06:00015570 - Trees, grids, and MSO decidability: From graphs to matroids (2006)
Výsledek druhu J RIV/00216224:14330/06:00015726 - Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (2006)
Výsledek druhu J RIV/00216224:14330/06:00015726 - Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (2006)
Výsledek druhu J RIV/00216224:14330/06:00015726 - Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (2006)
Výsledek druhu J RIV/00216224:14330/06:00015726 - Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (2006)
Výsledek druhu D RIV/00216224:14330/06:00015807 - On Matroid Representability and Minor Problems (2006)
Výsledek druhu D RIV/00216224:14330/06:00015807 - On Matroid Representability and Minor Problems (2006)
Výsledek druhu J RIV/00216224:14330/06:00015807 - On Matroid Representability and Minor Problems (2006)
Výsledek druhu J RIV/00216224:14330/06:00015807 - On Matroid Representability and Minor Problems (2006)
Výsledek druhu O RIV/00216224:14330/06:00024640 - On decidability of MSO theories of combinatorial structures: Towards general matroids? (2006)
Výsledek druhu O RIV/00216224:14330/06:00024640 - On decidability of MSO theories of combinatorial structures: Towards general matroids? (2006)
Výsledek druhu O RIV/00216224:14330/06:00024641 - MACEK - Real Structural Computations with Representable Matroids. (2006)
Výsledek druhu O RIV/00216224:14330/06:00024641 - MACEK - Real Structural Computations with Representable Matroids. (2006)
Výsledek druhu O RIV/00216224:14330/06:00024654 - On the Crossing Number of Almost Planar Graphs (2006)
Výsledek druhu O RIV/00216224:14330/06:00024654 - On the Crossing Number of Almost Planar Graphs (2006)
Výsledek druhu O RIV/00216224:14330/06:00024656 - A note on multicriteria decision making (2006)
Výsledek druhu O RIV/00216224:14330/06:00024656 - A note on multicriteria decision making (2006)
Výsledek druhu J RIV/00216224:14330/07:00020008 - Some Hard Problems on Matroid Spikes (2007)
Výsledek druhu J RIV/00216224:14330/07:00020008 - Some Hard Problems on Matroid Spikes (2007)
Výsledek druhu J RIV/00216224:14330/07:00020090 - Width Parameters Beyond Tree-width and Their Applications (2007)
Výsledek druhu J RIV/00216224:14330/07:00020090 - Width Parameters Beyond Tree-width and Their Applications (2007)
Výsledek druhu J RIV/00216224:14330/07:00020090 - Width Parameters Beyond Tree-width and Their Applications (2007)
Výsledek druhu D RIV/00216224:14330/07:00020423 - Approximating the Crossing Number of Toroidal Graphs (2007)
Výsledek druhu D RIV/00216224:14330/07:00020423 - Approximating the Crossing Number of Toroidal Graphs (2007)
Výsledek druhu J RIV/00216224:14330/07:00020424 - The crossing number of a projective graph is quadratic in the face--width (Extended abstract) (2007)
Výsledek druhu J RIV/00216224:14330/07:00020424 - The crossing number of a projective graph is quadratic in the face--width (Extended abstract) (2007)
Výsledek druhu O RIV/00216224:14330/07:00024642 - The crossing number of a projective graph is quadratic in the face-width (2007)
Výsledek druhu O RIV/00216224:14330/07:00024642 - The crossing number of a projective graph is quadratic in the face-width (2007)
Výsledek druhu O RIV/00216224:14330/07:00024653 - New almost-planar crossing-critical graph families (2007)
Výsledek druhu O RIV/00216224:14330/07:00024653 - New almost-planar crossing-critical graph families (2007)
Výsledek druhu O RIV/00216224:14330/07:00024655 - Finding Branch-decompositions and Rank-decompositions (2007)
Výsledek druhu O RIV/00216224:14330/07:00024655 - Finding Branch-decompositions and Rank-decompositions (2007)
Výsledek druhu J RIV/61989100:27240/05:00012169 - A Parametrized Algorithm for Matroid Branch-Width (2005)
Výsledek druhu J RIV/61989100:27240/05:00012170 - Computing the Tutte Polynomial on Graphs of Bounded Clique-Width, extended abstract (2005)
Výsledek druhu A RIV/61989100:27240/05:00012171 - Computing the Tutte Polynomial with Restricted "Width" (2005)
Výsledek druhu A RIV/61989100:27240/05:00012172 - Matroidy v teoretické informatice (2005)
Výsledek druhu A RIV/61989100:27240/05:00012173 - On Crossing-Critical Graphs (2005)
Výsledek druhu D RIV/61989100:27240/05:00012174 - Width parameters of graphs and matroids (2005)
Výsledek druhu A RIV/61989100:27240/05:00012175 - Matroid Tree-Width and Chordality (2005)
Výsledek druhu J RIV/61989100:27240/06:00013584 - On matroid representability and minor problems (2006)
Výsledek druhu J RIV/61989100:27240/06:00013585 - Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids (2006)
Výsledek druhu J RIV/61989100:27240/06:00013587 - Crossing Number is Hard for Cubic Graphs (2006)
Výsledek druhu M RIV/61989100:27240/06:00013588 - Crossing number of almost planar graphs (2006)
Výsledek druhu W RIV/61989100:27240/06:00013589 - On decidability of MSO theories of combinatorial structures: Towards general matroids? (2006)
Výsledek druhu J RIV/61989100:27240/06:00013590 - Trees, grids, and MSO decidability: From graphs to matroids (2006)
Výsledek druhu W RIV/61989100:27240/06:00013591 - MACEK - real structural computations with matroids (2006)
Výsledek druhu D RIV/61989100:27240/07:00014964 - Approximating the Crossing Number of Toroidal Graphs (2007)
Výsledek druhu J RIV/61989100:27240/07:00014965 - The crossing number of a projective graph is quadratic in the face--width (Extended abstract) (2007)
Výsledek druhu J RIV/61989100:27240/07:00015019 - Some Hard Problems on Matroid Spikes (2007)

Hodnocení dokončeného projektu

Hodnocení výsledků V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků řešení česky V rámci řešení našeho projektu bylo objeveno množství nových teoretických poznatků v oblastech strukturálních a topologických vlastností kombinatorických struktur (především grafů a matroidů) a jejich algoritmických aplikacích. Tyto nové výsledky byly př
Vyhledávání ...