Skip to main content

7 Result(s)

within Tomáš Gavenčiak Remove this filter

and

  1. Article

    Open Access

    Understanding the effectiveness of government interventions against the resurgence of COVID-19 in Europe

    European governments use non-pharmaceutical interventions (NPIs) to control resurging waves of COVID-19. However, they only have outdated estimates for how effective individual NPIs were in the first wave. We ...

    Mrinank Sharma, Sören Mindermann, Charlie Rogers-Smith… in Nature Communications (2021)

    Download PDF (4026 KB) View Article

  2. No Access

    Article

    Sorting by Swaps with Noisy Comparisons

    We study sorting of permutations by random swaps if each comparison gives the wrong result with some fixed probability \(p<1/2\) ...

    Tomáš Gavenčiak, Barbara Geissmann, Johannes Lengler in Algorithmica (2019)

  3. No Access

    Chapter and Conference Paper

    Compact I/O-Efficient Representation of Separable Graphs and Optimal Tree Layouts

    Compact and I/O-efficient data representations play an important role in efficient algorithm design, as memory bandwidth and latency can present a significant performance bottleneck, slowing the computation by...

    Tomáš Gavenčiak, Jakub Tětek in Theory and Applications of Models of Computation (2019)

  4. No Access

    Chapter and Conference Paper

    Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems

    We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neighborhood diversity and clique ...

    Jiří Fiala, Tomáš Gavenčiak, Dušan Knop, Martin Koutecký… in Computing and Combinatorics (2016)

  5. No Access

    Chapter and Conference Paper

    Cops and Robbers on String Graphs

    The game of cops and robber, introduced by Nowakowski and Winkler in 1983, is played by two players on a graph. One controls k cops and the other a robber. The players alternate and move their pieces to the dista...

    Tomáš Gavenčiak, Przemysław Gordinowicz, Vít Jelínek… in Algorithms and Computation (2015)

  6. No Access

    Chapter and Conference Paper

    Deciding First Order Properties of Matroids

    Frick and Grohe [J. ACM 48 (2006), 1184–1206] introduced a notion of graph classes with locally bounded tree-width and established that every first order property can be decided in almost linear time in such a...

    Tomáš Gavenčiak, Daniel Král, Sang-il Oum in Automata, Languages, and Programming (2012)

  7. No Access

    Chapter and Conference Paper

    Catching a Fast Robber on Interval Graphs

    We analyse the Cops and ∞-fast Robber game on the class of interval graphs and show it to be polynomially decidable on such graphs. This solves an open problem posed in paper “Pursuing a fast robber on a graph...

    Tomáš Gavenčiak in Theory and Applications of Models of Computation (2011)