Zobrazeno 1 - 10
of 22
pro vyhledávání: '"Folwarczný, Lukáš"'
[Alecu et al.: Graph functionality, JCTB2021] define functionality, a graph parameter that generalizes graph degeneracy. They research the relation of functionality to many other graph parameters (tree-width, clique-width, VC-dimension, etc.). Extend
Externí odkaz:
http://arxiv.org/abs/2302.11862
Autor:
Bourneuf, Romain, Folwarczný, Lukáš, Hubáček, Pavel, Rosen, Alon, Schwartzbach, Nikolaj Ignatieff
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on monochromatic subgraphs and the Erd\H{o}s-Rado sunflower lemma. Implicit v
Externí odkaz:
http://arxiv.org/abs/2209.04827
Autor:
Folwarczný, Lukáš
Feasible interpolation is a general technique for proving proof complexity lower bounds. The monotone version of the technique converts, in its basic variant, lower bounds for monotone Boolean circuits separating two NP-sets to proof complexity lower
Externí odkaz:
http://arxiv.org/abs/2201.05662
Autor:
Folwarczný, Lukáš
Graph communication protocols are a generalization of classical communi- cation protocols to the case when the underlying graph is a directed acyclic graph. Motivated by potential applications in proof complexity, we study variants of graph communica
Externí odkaz:
http://www.nusl.cz/ntk/nusl-388119
Autor:
Bienkowski, Marcin, Böhm, Martin, Byrka, Jaroslaw, Chrobak, Marek, Dürr, Christoph, Folwarczný, Lukáš, Jeż, Łukasz, Sgall, Jiří, Thang, Nguyen Kim, Veselý, Pavel
In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pen
Externí odkaz:
http://arxiv.org/abs/1507.02378
Autor:
Folwarczný, Lukáš, Knop, Dušan
IV-matching is a generalization of perfect bipartite matching. The complexity of finding IV-matching in a graph was posted as an open problem at the ICALP 2014 conference. In this note, we resolve the question and prove that, contrary to the expectat
Externí odkaz:
http://arxiv.org/abs/1506.08388
Autor:
Folwarczný, Lukáš, Sgall, Jiří
Caching (also known as paging) is a classical problem concerning page replacement policies in two-level memory systems. General caching is the variant with pages of different sizes and fault costs. We give the first NP-hardness result for general cac
Externí odkaz:
http://arxiv.org/abs/1506.07905
Publikováno v:
Bourneuf, R, Folwarczný, L, Hubáček, P, Rosen, A & Schwartzbach, N I 2023, PPP-Completeness and Extremal Combinatorics . i 14th Conference on Innovations in Theoretical Computer Science . s. 1-20 . https://doi.org/10.4230/LIPIcs.ITCS.2023.22
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey’s theorem on monochromatic subgraphs and the Erdős-Rado sunflower lemma. Implicit ve
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2a53dae3ec07852141eaf0188ba94035
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Bienkowski, Marcin, Böhm, Martin, Byrka, Jaroslaw, Chrobak, Marek, Dürr, Christoph, Folwarczný, Lukáš, Jeż, Łukasz, Sgall, Jiří, Thang, Nguyen Kim, Veselý, Pavel
Publikováno v:
Operations Research; Jan/Feb2020, Vol. 68 Issue 1, p214-232, 19p, 2 Diagrams, 1 Chart, 2 Graphs