. "2010-04-16+02:00"^^ . "Utilization of structural and %22Width%22 parameters in combinatorics and algorithmic complexity"@en . . . . "0"^^ . "http://www.isvav.cz/projectDetail.do?rowId=GA201/08/0308"^^ . "1"^^ . . . "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 of directed graphs having algorithmic applications. With a new development and start of collaboration with colleagues from RWTH Aachen (bilateral g"@en . "2008-01-01+01:00"^^ . . " graph searching" . "0"^^ . " fixed parameter algorithms" . . "V n\u00E1vrhu na\u0161eho projektu z roku 2007 byly nast\u00EDn\u011Bny tyto t\u0159i hlavn\u00ED sm\u011Bry v\u011Bdeck\u00E9ho b\u00E1d\u00E1n\u00ED: (1) v\u00FDzkum struktur\u00E1ln\u00EDch \u0161\u00ED\u0159kov\u00FDch parametr\u016F a dekompozic graf\u016F a matroid\u016F, (2) v\u00FDzkum p\u0159edev\u0161\u00EDm algoritmick\u00FDch hledisek pr\u016Fse\u010D\u00EDkov\u00E9ho \u010D\u00EDsla graf\u016F, (3) v\u00FDzkum nov\u00FDch struktur\u00E1ln\u00EDch parametr\u016F orientovan\u00FDch graf\u016F s algoritmick\u00FDmi aplikacemi. V pr\u016Fb\u011Bhu \u0159e\u0161en\u00ED a v souvislosti s nav\u00E1z\u00E1n\u00EDm spolupr\u00E1ce s t\u00FDmem z"@cs . . "20"^^ . " graph minors" . "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."@en . "20"^^ . . . "2015-02-09+01:00"^^ . . . . . "2010-12-31+01:00"^^ . . . "Mnoho praktick\u00FDch algoritmick\u00FDch ot\u00E1zek m\u00E1 j\u00E1dro zalo\u017Een\u00E9 na kombinatorick\u00FDch struktur\u00E1ch jako jsou grafy, orientovan\u00E9 grafy \u010Di matroidy. A\u010Dkoliv je typick\u00E9, \u017Ee na v\u011Bt\u0161inu t\u011Bchto probl\u00E9m\u016F nem\u00E1me \u017E\u00E1dn\u00E1 obecn\u00E1 efektivn\u00ED algoritmick\u00E1 \u0159e\u0161en\u00ED, \u010Dasto jsme schopni je efektivn\u011B vy\u0159e\u0161it pro v\u0161echny vstupy maj\u00EDc\u00ED vhodnou vnit\u0159n\u00ED strukturu jako nap\u0159\u00EDklad omezenou \u0161\u00ED\u0159ku. Na\u0161im pl\u00E1nem je zkoumat a d\u00E1le zobecnit u\u017Eite\u010Dn\u00E1 obs\u00E1hl\u00E1 vyu\u017Eit\u00ED struktur\u00E1ln\u00EDch \u0161\u00ED\u0159kov\u00FDch parametr\u016F kombinatoriky (jako jsou stromov\u00E1, v\u011Btven\u00E1, klikov\u00E1, DAG- \u010Di rankov\u00E1 \u0161\u00ED\u0159ka, kter\u00E9 ji\u017E v\u0161echny byly shled\u00E1ny velmi u\u017Eite\u010Dn\u00FDmi) p\u0159i navrhov\u00E1n\u00ED nov\u00FDch efektivn\u00EDch parametrizovan\u00FDch algoritm\u016F, p\u0159i \u0159e\u0161en\u00ED ot\u00E1zek rozhodnutelnosti logick\u00FDch teori\u00ED a dokazov\u00E1n\u00ED nov\u00FDch struktur\u00E1ln\u00EDch v\u011Bt o kombinatorick\u00FDch objektech. Pl\u00E1n navazuje na n\u00E1\u0161 p\u0159edchoz\u00ED obdobn\u00FD \u00FAsp\u011B\u0161n\u00FD v\u00FDzkum (zhruba od roku 2001)." . "tree-width" . "GA201/08/0308" . "Vyu\u017Eit\u00ED struktur\u00E1ln\u00EDch a %22\u0161\u00ED\u0159kov\u00FDch%22 parametr\u016F v kombinatorice a algoritmick\u00E9 slo\u017Eitosti" . . "tree-width; fixed parameter algorithms; graph minors; graph searching; crossing number"@en . .