Utilization of structural and "Width" parameters in combinatorics and algorithmic complexity
Project goals
Many practical algorithmic problems have a core based on combinatorial structures, such as graphs, digraphs, or matroids. Although it is typically infeasible to give general algorithmic solutions of (majority of) these problems, it is often the case thatsuch hard problems are indeed efficiently solvable for all inputs of certain internal structure like those having bounded width.Our research plan is to investigate and generalize the deep and interesting applications of structural width parameters in combinatorics (e.g. tree-width, branch-width, clique-width, DAG-width, or rank-width, which all have already proved to be very useful) to efficient parametrized algorithm design, decidability questions of theories in MSO logic, and new structural theorems about the underlying objects. This plan builds on our previous successful research (since about 2001) in the indicated directions.
Keywords
tree-widthfixed parameter algorithmsgraph minorsgraph searchingcrossing number
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 11 (SGA02008GA-ST)
Main participants
—
Contest type
VS - Public tender
Contract ID
201/08/0308
Alternative language
Project name in Czech
Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti
Annotation in Czech
Mnoho praktických algoritmických otázek má jádro založené na kombinatorických strukturách jako jsou grafy, orientované grafy či matroidy. Ačkoliv je typické, že na většinu těchto problémů nemáme žádná obecná efektivní algoritmická řešení, často jsme schopni je efektivně vyřešit pro všechny vstupy mající vhodnou vnitřní strukturu jako například omezenou šířku. Našim plánem je zkoumat a dále zobecnit užitečná obsáhlá využití strukturálních šířkových parametrů kombinatoriky (jako jsou stromová, větvená, kliková, DAG- či ranková šířka, které již všechny byly shledány velmi užitečnými) při navrhování nových efektivních parametrizovaných algoritmů, při řešení otázek rozhodnutelnosti logických teorií a dokazování nových strukturálních vět o kombinatorických objektech. Plán navazuje na náš předchozí obdobný úspěšný výzkum (zhruba od roku 2001).
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BA - General mathematics
CEP - secondary branch
IN - Informatics
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 from 2007 has outlined the following three research directions: studying (1) structural width parameters and decompositions of graphs and matroids, (2) mainly algorithmic aspects of graph crossing numbers, and (3) new structural parameters ofdirected graphs having algorithmic applications. With a new development and start of collaboration with colleagues from RWTH Aachen (bilateral g
Solution timeline
Realization period - beginning
Jan 1, 2008
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-GA-U/03:3
Data delivery date
Feb 9, 2015
Finance
Total approved costs
946 thou. CZK
Public financial support
946 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
946 CZK thou.
Public support
946 CZK thou.
0%
Provider
Czech Science Foundation
CEP
BA - General mathematics
Solution period
01. 01. 2008 - 31. 12. 2010