| Attributes | Values |
|---|
| rdf:type
| |
| Description
| - 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 (cs)
- 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)
|
| Title
| - Structural graph theory and parameterized complexity (en)
- Strukturální teorie grafů a parametrizovaná složitost (cs)
|
| http://linked.open...vai/cislo-smlouvy
| |
| http://linked.open...avai/druh-souteze
| |
| http://linked.open...domain/vavai/faze
| |
| http://linked.open...vavai/hlavni-obor
| |
| http://linked.open...vai/vedlejsi-obor
| |
| http://linked.open...vavai/id-aktivity
| |
| http://linked.open.../vavai/id-souteze
| |
| http://linked.open...n/vavai/kategorie
| |
| http://linked.open...vai/klicova-slova
| - fixed parameter tractability; exponential algorithm; tree-width; graph minor; topological graph (en)
|
| http://linked.open...avai/konec-reseni
| |
| http://linked.open...nujicich-prijemcu
| |
| http://linked.open...avai/poskytovatel
| |
| http://linked.open...avai/start-reseni
| |
| http://linked.open...ai/statni-podpora
| |
| http://linked.open...vavai/typProjektu
| |
| http://linked.open...ai/uznane-naklady
| |
| http://linked.open...ai/pocet-prijemcu
| |
| http://linked.open...cet-spoluprijemcu
| |
| http://linked.open...ai/pocet-vysledku
| |
| http://linked.open...ku-zverejnovanych
| |
| is http://linked.open...ain/vavai/projekt
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)