About: Parameterized algorithms and kernelization in the context of discrete mathematics and logic

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Parameterized algorithms and kernelization in the context of discrete mathematics and logic Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Projekt, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	http://linked.opendata.cz/ontology/domain/vavai/Projekt
rdfs:seeAlso	http://www.isvav.cz/projectDetail.do?rowId=GA14-03501S
Description	Jeden z možných přístupů ke zdolání zdánlivě nepřekonatelné překážky NP-těžkosti algoritmických problémů nám podává teorie parametrizované složitosti: Vstup těžkého problému je opatřen doplňkovým parametrem - libovolným číslem k, jehož jakákoliv počitatelná funkce omezuje výpočetní složitost našeho problému. Snahou je volit parametr k tak, aby jeho hodnota byla na zajímavých vstupech nízká, což následně umožňuje efektivní řešení problémů na takto charakterizovaných vstupech. V projektu budou hledány a studovány vhodné strukturální a geometrické parametry pro třídy kombinatorických objektů (grafů) a nové poznatky budou využity v návrhu lepších parametrizovaných algoritmů a obecných logikou popsaných tzv. algoritmických metavět. Mimo jiné bude pokračovat nedávno velmi úspěšné nalézání dolních mezí parametrizované řešitelnosti problémů. Mezi novými směry výzkumu v navržené oblasti jsou především zmíněny oblasti metavět pro kernelizaci (efektivní parametrické předzpracování) problémů a využití geometrických parametrů (vycházejících například z reprezentace vstupního grafu). 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)
Title	Parameterized algorithms and kernelization in the context of discrete mathematics and logic (en) Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
skos:notation	GA14-03501S
http://linked.open...avai/cep/aktivita	Standard projects
http://linked.open...kovaStatniPodpora	http://linked.opendata.cz/resource/domain/vavai/projekt/GA14-03501S/celkovaStatniPodpora
http://linked.open...ep/celkoveNaklady	http://linked.opendata.cz/resource/domain/vavai/projekt/GA14-03501S/celkoveNaklady
http://linked.open...datumDodatniDoRIV	2015-04-23 (xsd:date)
http://linked.open...i/cep/druhSouteze	VS - Veřejná soutěž ve výzkumu a vývoji
http://linked.open...ep/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open.../cep/fazeProjektu	100787859
http://linked.open...ai/cep/hlavniObor	IN - Informatika
http://linked.open...vai/cep/kategorie	ZV - Základní výzkum
http://linked.open.../cep/klicovaSlova	parameterized complexity; kernelization; algorithmic metatheorems; complexity lower bounds; MSO logic; graphs (en)
http://linked.open...ep/partnetrHlavni	Fakulta informatiky
http://linked.open...inujicichPrijemcu	0 (xsd:int)
http://linked.open...cep/pocetPrijemcu	1 (xsd:int)
http://linked.open...ocetSpoluPrijemcu	0 (xsd:int)
http://linked.open.../pocetVysledkuRIV	1 (xsd:int)
http://linked.open...enychVysledkuVRIV	1 (xsd:int)
http://linked.open...lneniVMinulemRoce	2014-02-25 (xsd:date)
http://linked.open.../prideleniPodpory	http://linked.opendata.cz/resource/domain/vavai/cep/prideleniPodpory/14-03501S
http://linked.open...iciPoslednihoRoku	2015
http://linked.open...atUdajeProjZameru	2015
http://linked.open.../vavai/cep/soutez	SGA0201400001
http://linked.open...usZobrazovaneFaze	DRRVB
http://linked.open...ai/cep/typPojektu	P - Projekt výzkumu a vývoje financovaný ze státního rozpočtu
http://linked.open...ep/ukonceniReseni	2016-12-31 (xsd:date)
http://linked.open...ep/zahajeniReseni	2014-01-01 (xsd:date)
http://linked.open...tniCyklusProjektu	ZB
http://linked.open.../cep/klicoveSlovo	parameterized complexity MSO logic algorithmic metatheorems complexity lower bounds kernelization
is http://linked.open...vavai/riv/projekt of	Faster Existential FO Model Checking on Posets
is http://linked.open...vavai/cep/projekt of	http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GA14-03501S/2014/orjk%3A14330 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GA14-03501S/2015/orjk%3A14330 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GA14-03501S/2016/orjk%3A14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 114 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software