About: Structural graph theory and parameterized complexity

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

About: Structural graph theory and parameterized 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=GC201/09/J021
Description	Many real-world algorithmic problems turn out to be intractable in their full generality. Theory of parameterized complexity, however, provides a useful framework for a refined analysis of such hard problems, and for designing conceptually new algorithmsthat can solve hard problems for the real-world instances efficiently. In contrast to heuristics, this approach provides guarantied runtime bounds.Graphs are combinatorial structures suitable for modeling many discrete and optimization problems. Structural graph theory has already proved very useful in parameterized algorithmics. For instance, most of traditional hard problems are efficiently solvable on graphs of bounded tree-width. We plan to exploit other structural properties of graphs like branch-width, DAG-width, rank-width, or their topological properties. Our goal is to find new application areas of structural graph theory in parameterized algorithm design, by collaboration of our research groups from both areas. (en) Mnoho algoritmických problémů z reálného světa se ukazují jako nezvladatelné v plné obecnosti. Teorie parametrizované složitosti nám však dává užitečný rámec nástrojů pro jemnější analýzu obtížnosti těchto těžkých problémů a pro návrh koncepčně nových algoritmů, které dokáží řešit reálné instance těžkých problémů efektivněji. Na rozdíl od heuristických přístupů tak získáme i garantované ohraničení času. Grafy jako kombinatorické struktury jsou vhodné pro modelování diskrétních a optimalizačních problémů. Přitom strukturální teorie grafů se ukazuje jako velmi užitečná v parametrizovaných algoritmech. Například většina tradičně těžkých problémů je rychle řešitelná na grafech omezené stromové šířky.Naším plánem je využít i další strukturální vlastnosti grafů jako větvená šířka, DAG šířka, ranková šířka, či jejich topologické vlastnosti. Cílem je nalézt nové oblasti aplikací strukturální teorie grafů v navrhování parametrizovaných algoritmů, čehož bude dosaženo spoluprácí našich výzkumných
Title	Structural graph theory and parameterized complexity (en) Strukturální teorie grafů a parametrizovaná složitost
skos:notation	GC201/09/J021
http://linked.open...avai/cep/aktivita	International projects
http://linked.open...kovaStatniPodpora	http://linked.opendata.cz/resource/domain/vavai/projekt/GC201%2F09%2FJ021/celkovaStatniPodpora
http://linked.open...ep/celkoveNaklady	http://linked.opendata.cz/resource/domain/vavai/projekt/GC201%2F09%2FJ021/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	82560081
http://linked.open...ai/cep/hlavniObor	IN - Informatika
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	fixed parameter tractability; exponential algorithm; tree-width; graph minor; topological graph (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	14 (xsd:int)
http://linked.open...enychVysledkuVRIV	14 (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%2F09%2FJ021
http://linked.open...iciPoslednihoRoku	2010
http://linked.open...atUdajeProjZameru	2011
http://linked.open.../vavai/cep/soutez	SGA02009GA1GC
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	BA - Obecná matematika
http://linked.open...ep/zahajeniReseni	2009-01-01 (xsd:date)
http://linked.open...jektu+dodavatelem	First we gave a thorough overview of parameterized complexity of known problems on directed graphs with respect to known directed “width” measures. Moreover, we showed that most of these problems remain NP-complete even for very restricted classes of directed graphs (using two new measures DAG-depth and K-width). Some of the complexity bounds were taken from literature, however the rest was prove (en) Dosažené výsledky jsou následující: Za prvé jsme podali komplexní přehled parametrizované složitosti řešení známých grafových problému pro orientované grafy vzhledem ke  známým strukturálním mírám (“šířkám”).  Navíc jsme ukázali, že většina těchto problémů zůstává NP-těžká i pro velmi omezené podtřídy acyklických grafů (viz dvě nově zavedené specializované míry DAG-depth a K-width.)&nbs (cs)
http://linked.open...tniCyklusProjektu	ZKU
http://linked.open.../cep/klicoveSlovo	fixed parameter tractability exponential algorithm graph minor tree-width
is http://linked.open...vavai/riv/projekt of	Digraph width measures in parameterized algorithmics On Digraph Width Measures in Parameterized Algorithmics Are there any good digraph width measures? Thread graphs, linear rank-width and their algorithmic applications The DAG-width of directed graphs Unified Approach to Polynomial Algorithms on Graphs of Bounded (bi-)Rank-width Czech-Slovak Conference GRAFY 2010 New Results on the Complexity of the Max- and Min-Rep Problems Algorithmic applications of linear rank-width New results on the complexity of oriented colouring on restricted digraph classes Proceedings of the 45th Czech-Slovak Conference GRAFY 2010 On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width New Results on the Complexity of the Max- and Min-Rep Problems Better algorithms for satisfiability problems for formulas of bounded rank-width
is http://linked.open...vavai/cep/projekt of	http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GC201%2F09%2FJ021/2009/orjk%3A14330 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GC201%2F09%2FJ021/2010/orjk%3A14330 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GC201%2F09%2FJ021/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, 110 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software