Well-structured combinatorial classes, width parameters, and design of efficient algorithms
Project goals
Many important algorithmic problems are known to be NP-hard and thus it is unlikely that they could be solved efficiently on all possible inputs. One approach to cope with such problems is the use of parameterized complexity theory: the difficulty of inputs is classified by an additional parameter and algorithms are designed to efficiently solve problems on inputs with a bounded parameter. Our goal is to obtain new structural results on classes of (sparse) combinatorial objects, particularly on objectswith bounded width parameters, and apply these new results in the design of parameterized algorithms.
Keywords
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 14 (SGA02011GA-ST)
Main participants
—
Contest type
VS - Public tender
Contract ID
P202-11-0196
Alternative language
Project name in Czech
Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
Annotation in Czech
Je známo, že řada důležitých algoritmických problémů je NP-úplná, a neočekává se, že takovéto problémy by byly řešitelné efektivními algoritmy pro všechny možné vstupy. Jedna z oblastí, která studuje možnosti řešení takových algoritmických problémů, je teorie parametrizované složitosti: obtížnost vstupů je popsána novým parametrem a hledají se algoritmy, které efektivně vyřeší vstupy, jejichž obtížnost je parametrem omezena. Cílem předkládaného projektu je nalezení nových strukturálních výsledků o třídách (řídkých) kombinatorických struktur, zejména objektů s omezenými šířkovými parametry, a využití nově získaných poznatků v návrhu parametrizovaných algoritmů.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
BA - General mathematics
CEP - another secondary branch
—
10101 - Pure mathematics
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
The project obtained new structural results of cutting edge quality on classes of (sparse) combinatorial objects, particularly on objects with bounded width parameters, and applied these new results in the design of parameterized algorithms.
Solution timeline
Realization period - beginning
Jan 1, 2011
Realization period - end
Dec 31, 2013
Project status
U - Finished project
Latest support payment
Jun 7, 2013
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
CEP14-GA0-GA-U/01:1
Data delivery date
Jul 1, 2014
Finance
Total approved costs
4,928 thou. CZK
Public financial support
4,928 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
4 928 CZK thou.
Public support
4 928 CZK thou.
100%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2011 - 31. 12. 2013