. " algorithmic metatheorems" . "1"^^ . "0"^^ . . . "1"^^ . "parameterized complexity; kernelization; algorithmic metatheorems; complexity lower bounds; MSO logic; graphs"@en . "2015-04-23+02:00"^^ . " kernelization" . "0"^^ . "Parameterized algorithms and kernelization in the context of discrete mathematics and logic"@en . . . . "GA14-03501S" . "2016-12-31+01:00"^^ . "2014-02-25+01:00"^^ . . . "Jeden z mo\u017En\u00FDch p\u0159\u00EDstup\u016F ke zdol\u00E1n\u00ED zd\u00E1nliv\u011B nep\u0159ekonateln\u00E9 p\u0159ek\u00E1\u017Eky NP-t\u011B\u017Ekosti algoritmick\u00FDch probl\u00E9m\u016F n\u00E1m pod\u00E1v\u00E1 teorie parametrizovan\u00E9 slo\u017Eitosti: Vstup t\u011B\u017Ek\u00E9ho probl\u00E9mu je opat\u0159en dopl\u0148kov\u00FDm parametrem - libovoln\u00FDm \u010D\u00EDslem k, jeho\u017E jak\u00E1koliv po\u010Ditateln\u00E1 funkce omezuje v\u00FDpo\u010Detn\u00ED slo\u017Eitost na\u0161eho probl\u00E9mu. Snahou je volit parametr k tak, aby jeho hodnota byla na zaj\u00EDmav\u00FDch vstupech n\u00EDzk\u00E1, co\u017E n\u00E1sledn\u011B umo\u017E\u0148uje efektivn\u00ED \u0159e\u0161en\u00ED probl\u00E9m\u016F na takto charakterizovan\u00FDch vstupech. V projektu budou hled\u00E1ny a studov\u00E1ny vhodn\u00E9 struktur\u00E1ln\u00ED a geometrick\u00E9 parametry pro t\u0159\u00EDdy kombinatorick\u00FDch objekt\u016F (graf\u016F) a nov\u00E9 poznatky budou vyu\u017Eity v n\u00E1vrhu lep\u0161\u00EDch parametrizovan\u00FDch algoritm\u016F a obecn\u00FDch logikou popsan\u00FDch tzv. algoritmick\u00FDch metav\u011Bt. Mimo jin\u00E9 bude pokra\u010Dovat ned\u00E1vno velmi \u00FAsp\u011B\u0161n\u00E9 nal\u00E9z\u00E1n\u00ED doln\u00EDch mez\u00ED parametrizovan\u00E9 \u0159e\u0161itelnosti probl\u00E9m\u016F. Mezi nov\u00FDmi sm\u011Bry v\u00FDzkumu v navr\u017Een\u00E9 oblasti jsou p\u0159edev\u0161\u00EDm zm\u00EDn\u011Bny oblasti metav\u011Bt pro kernelizaci (efektivn\u00ED parametrick\u00E9 p\u0159edzpracov\u00E1n\u00ED) probl\u00E9m\u016F a vyu\u017Eit\u00ED geometrick\u00FDch parametr\u016F (vych\u00E1zej\u00EDc\u00EDch nap\u0159\u00EDklad z reprezentace vstupn\u00EDho grafu)." . "2014-01-01+01:00"^^ . . . "A possible approach to overcome the notorious intractability of NP-hard problems is provided by the theory of Parameterized Complexity: an auxiliary %22parameter%22 - an arbitrary number k - is assigned to each input, such that a computable function of k upper-bounds the computational complexity of the problem. The general goal here is to choose a parameter k which attains low values on interesting inputs, thus leading to efficient algorithms on inputs characterized by such k. The project will search for suitable structural and geometric parameters for classes of combinatorial objects (graphs) and use the new findings to obtain more efficient parameterized algorithms, as well as, so-called algorithmic metatheorems based on logic description. In particular, it will continue the recent very successful research of parameterized complexity lower bounds. Metatheorems for kernelization (parameterized preprocessing) of problems, and search for usable geometric parameters (e.g., coming from an input representation of the graph) are specifically mentioned among the new research tasks."@en . " MSO logic" . "Parametrizovan\u00E9 algoritmy a kernelizace v kontextu diskr\u00E9tn\u00ED matematiky a logiky" . " complexity lower bounds" . . . "http://www.isvav.cz/projectDetail.do?rowId=GA14-03501S"^^ . . . "1"^^ . . "parameterized complexity" . . .