Název projektu
Strukturální vlastnosti a algoritmická složitost diskrétních problémů
Kód
GA201/05/0050
Předmět výzkumu
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. Ja ko 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.
Rok zahájení
2005
Rok ukončení
2007
Poskytovatel
Grantová agentura ČR
Kategorie
Obecná forma
Typ
Standardní projekty
Řešitel
Informační systém výzkumu, vývoje a inovací