About: Utilization of structural and %22Width%22 parameters in combinatorics and algorithmic complexity

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

About: Utilization of structural and %22Width%22 parameters in combinatorics and algorithmic complexity 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=GA201/08/0308
Description	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) 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).
Title	Utilization of structural and %22Width%22 parameters in combinatorics and algorithmic complexity (en) Využití strukturálních a %22šířkových%22 parametrů v kombinatorice a algoritmické složitosti
skos:notation	GA201/08/0308
http://linked.open...avai/cep/aktivita	Standard projects
http://linked.open...kovaStatniPodpora	http://linked.opendata.cz/resource/domain/vavai/projekt/GA201%2F08%2F0308/celkovaStatniPodpora
http://linked.open...ep/celkoveNaklady	http://linked.opendata.cz/resource/domain/vavai/projekt/GA201%2F08%2F0308/celkoveNaklady
http://linked.open...datumDodatniDoRIV	2015-02-09 (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	82299303
http://linked.open...ai/cep/hlavniObor	BA - Obecná matematika
http://linked.open...hodnoceniProjektu	V - Vynikající výsledky (s mezinárodním významem apod.). Zároveň byly splněny cíle a předpokládané výsledky uvedené ve smlouvě / rozhodnutí o poskytnutí podpory.
http://linked.open...vai/cep/kategorie	ZV - Základní výzkum
http://linked.open.../cep/klicovaSlova	tree-width; fixed parameter algorithms; graph minors; graph searching; crossing number (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	20 (xsd:int)
http://linked.open...enychVysledkuVRIV	20 (xsd:int)
http://linked.open...lneniVMinulemRoce	2010-04-16 (xsd:date)
http://linked.open.../prideleniPodpory	http://linked.opendata.cz/resource/domain/vavai/cep/prideleniPodpory/201%2F08%2F0308
http://linked.open...iciPoslednihoRoku	2010
http://linked.open...atUdajeProjZameru	2011
http://linked.open.../vavai/cep/soutez	SGA02008GA-ST
http://linked.open...usZobrazovaneFaze	DUU
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	2010-12-31 (xsd:date)
http://linked.open.../cep/vedlejsiObor	IN - Informatika
http://linked.open...ep/zahajeniReseni	2008-01-01 (xsd:date)
http://linked.open...jektu+dodavatelem	V návrhu našeho projektu z roku 2007 byly nastíněny tyto tři hlavní směry vědeckého bádání: (1) výzkum strukturálních šířkových parametrů a dekompozic grafů a matroidů, (2) výzkum především algoritmických hledisek průsečíkového čísla grafů, (3) výzkum nových strukturálních parametrů orientovaných grafů s algoritmickými aplikacemi. V průběhu řešení a v souvislosti s navázáním spolupráce s týmem z (cs) 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)
http://linked.open...tniCyklusProjektu	ZBKU
http://linked.open.../cep/klicoveSlovo	tree-width fixed parameter algorithms graph minors graph searching
is http://linked.open...vavai/cep/projekt of	http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GA201%2F08%2F0308/2008/orjk%3A14330 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GA201%2F08%2F0308/2009/orjk%3A14330 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GA201%2F08%2F0308/2010/orjk%3A14330 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GA201%2F08%2F0308/2011/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, 48 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software