Structural graph theory and parameterized complexity
Public support
Provider
Czech Science Foundation
Programme
International projects
Call for proposals
Mezinárodní projekty 3 (SGA02009GA1GC)
Main participants
—
Contest type
VS - Public tender
Contract ID
201/09/J021
Alternative language
Project name in Czech
Strukturální teorie grafů a parametrizovaná složitost
Annotation in Czech
Mnoho algoritmických problémů z reálného světa se ukazují jako nezvladatelné v plné obecnosti. Teorie parametrizované složitosti nám však dává užitečný rámec nástrojů pro jemnější analýzu obtížnosti těchto těžkých problémů a pro návrh koncepčně nových algoritmů, které dokáží řešit reálné instance těžkých problémů efektivněji. Na rozdíl od heuristických přístupů tak získáme i garantované ohraničení času. Grafy jako kombinatorické struktury jsou vhodné pro modelování diskrétních a optimalizačních problémů. Přitom strukturální teorie grafů se ukazuje jako velmi užitečná v parametrizovaných algoritmech. Například většina tradičně těžkých problémů je rychle řešitelná na grafech omezené stromové šířky.Naším plánem je využít i další strukturální vlastnosti grafů jako větvená šířka, DAG šířka, ranková šířka, či jejich topologické vlastnosti. Cílem je nalézt nové oblasti aplikací strukturální teorie grafů v navrhování parametrizovaných algoritmů, čehož bude dosaženo spoluprácí našich výzkumných
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
BA - General mathematics
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
10101 - Pure mathematics<br>10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
First we gave a thorough overview of parameterized complexity of known problems on directed graphs with respect to known directed ?width? measures. Moreover, we showed that most of these problems remain NP-complete even for very restricted classes of directed graphs (using two new measures DAG-depth and K-width). Some of the complexity bounds were taken from literature, however the rest was prove
Solution timeline
Realization period - beginning
Jan 1, 2009
Realization period - end
Dec 31, 2010
Project status
U - Finished project
Latest support payment
Apr 16, 2010
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
CEP11-GA0-GC-U/03:3
Data delivery date
Feb 9, 2015
Finance
Total approved costs
1,014 thou. CZK
Public financial support
1,014 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK