velikost textu

Výsledky projektu Strukturální teorie grafů a efektivni algoritmy

Výsledky

▼▲Typ výsledku ▼▲Autor celku ▼▲Název celku
(Celkem 13 zázn.)
Fiala, Jiří; Gavenčiak, Tomáš; Knop, Dušan; Koutecký, Martin; Kratochvíl, Jan. Parameterized complexity of distance labeling and uniform channel assignment problems. Discrete Applied Mathematics, 2017, sv. Special Issue: GROW 2015, s. n/a–n/a. ISSN 0166-218X. IF 0.722. [Článek v časopise]
Knop, Dušan; Masařík, Tomáš. Computational complexity of distance edge labeling. Discrete Applied Mathematics, 2017, sv. Special Issue: IWOCA 2015, s. n/a–n/a. ISSN 0166-218X. IF 0.722. [Článek v časopise]
článek je v tisku - již dostupný online
Knop, Dušan. Partitioning Graphs into Induced Subgraphs. In Drewes F., Martín-Vide C., Truthe B.. International Conference on Language and Automata Theory and Applications. : Springer, 2017. s. 338–350. ISBN 978-3-319-53732-0. [Článek ve sborníku]
Knop, Dušan; Masařík, Tomáš. Computational complexity of distance edge labeling. In Lipták Z., Smyth W.. International Workshop on Combinatorial Algorithms. : Springer, 2016. s. 287–298. ISBN 978-3-319-29515-2. [Článek ve sborníku]
Dvořák, Pavel; Knop, Dušan; Masařík, Tomáš . Anti-Path Cover on Sparse Graph Classes. In Bouda, Jan; Holík, Lukáš; Kofroň, Jan; Strejček, Jan; Rambousek, Adam. Proceedings 11th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science Telč, Czech Republic, 21st-23rd October 2016. : Open Publishing Association, 2016. s. 82–86. [Článek ve sborníku]
Knop, Dušan; Koutecký, Martin; Mnich, Matthias. Voting and Bribing in Single-Exponential Time. In Heribert Vollmer, Brigitte Vallée. 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017. s. 46:1–46:14. ISBN 978-3-95977-028-6. [Článek ve sborníku]
Fiala, Jiří; Gavenčiak, Tomáš; Knop, Dušan; Koutecký, Martin; Kratochvíl, Jan. Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems - (Extended Abstract). In Thang N. Dinh, My T. Thai. Computing and Combinatorics - 22nd International Conference, COCOON2016, Ho Chi Minh City, Vietnam, August 2-4, 2016, Proceedings. : Springer, 2016. s. 67–78. ISBN 978-3-319-42633-4. [Článek ve sborníku]
Dvořák, Pavel a Knop, Dušan. Parametrized Complexity of Length-Bounded Cuts and Multi-cuts. In Rahul Jain, Sanjay Jain, Frank Stephan. 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings. : Springer International Publishing, 2015. s. 441–452. ISBN 978-3-319-17141-8. [Článek ve sborníku]
Fiala, Jiří; Gavenčiak, Tomáš; Knop, Dušan; Koutecký, Martin; Kratochvíl, Jan, V práci studujeme parametrizovanou složitost zobrecněných L(p,q) obarvení. Jako parametr požíváme neighborhood diversity (zobecnění vertex cover). Ukazujeme jak FPT algoritmus (i pro problém Channel Assignment) pomocí vertex cover, pro neighborhood diversity pak pro později zmíněný problém pouze ve speciálním případě. Dále pak ukazujeme W[1]-těžkost pro speciální variantu Channel Assignment problému pro parametr clique-width. Výsledek nebyl přijat na konferenci IPEC2015. [Jiný výsledek]
Folwarczný, Lukáš a Knop, Dušan, Na prestižní konferenci ICALP 2014 byl prezentován výsledek o regulárních nakrytích rovinných grafů (Fiala, Klavík, Kratochvíl, Nedela: Algorithmic aspects of regular graph covers with application to planar graphs). V článku byl problém rozhodování regulárních nakrytí redukován na problém tzv. IV-párování (ve speciální bipartitních vrstevnatých grafech). Naším výsledkem je NP-úplnost tohoto problému již pro nejjednodušší možný případ (tj. pro graf se čtyřmi vrstvami). D. Knop prezentoval tento výsledek na workshopu ATCAGC 2015. [Jiný výsledek]
Knop, Dušan a Masařík, Tomáš, Na konferenci IWOCA 2015 T. Masařík prezentoval společný výsledek. Ukazujeme, že je NP-těžké rozhodnout zda existuje hranové L(2,1)-obarvení grafu používající nanejvýš (právě) k barev (pro libovolné k alespoň 5). Pro hodnoty 1 až 4 pak dán popis grafů, které mají dané obarvení. Ukazujeme tedy přesnou dichotomii tohoto problému. Prozatím není možné považovat za publikaci, jelikož zmíněná konference bude konferenční sborník teprve vydávat. [Jiný výsledek]
Knop, Dušan, parametrizovaný algoritmus, který ukazuje, že problém délkou omezeného řezu je ve třídě FPT, pokud je parametrem velikost vrcholového pokrytí vstupního grafu. Dále pak ukazují, že tento problém je W[1]-těžký v případě, že je parametrem cestová šířka. D. Knop prezentoval výsledky této práce na Bordeaux Graph Workshop, ve sborníku vyšel rozšířený abstrakt. [Jiný výsledek]
Koutecký, Martin, Řešení problémů "Kapacitovaná dominující množina" a "Vektorová dominující množina". Tyto problémy byly v minulosti zkoumány z hlediska jiných parametrů, například pro stromovou šířku jsou W[1]-těžké. Pro oba zmíněné problémy je ukázáno, že v případě parametrizace "neighbourhood diversity" náleží tyty problémy na třídy FPT za pomoci použití technik celočíselného lineárního programování. M. Koutecký prezentoval výsledky této práce na Bordeaux Graph Workshop, ve sborníku vyšel rozšířený abstrakt. [Jiný výsledek]