1 citations · 4 across the 22 of their papers we have counts for
7 papers · 1 filter
Exact Shortest Paths with Rational Weights on the Word RAM
Adam Karczmarz, Wojciech Nadara, Marek Sokołowski
Exact computation of shortest paths in weighted graphs has been traditionally studied in one of two settings. First, one can assume that the edge weights are real numbers and all t…
Fully dynamic approximation schemes on planar and apex-minor-free graphs
Tuukka Korhonen, Wojciech Nadara, Michał Pilipczuk +1
The classic technique of Baker [J. ACM '94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and…
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel +3
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence)…
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard
Łukasz Kowalik, Alexandra Lassota, Konrad Majewski +2
Let be a positive integer. For a finite set , we define its integer cone as the set $\mathsf{IntCone}(X) := \{ \sum_{x \in X} λ_x \cdot x \mid λ_x \in…
Dynamic treewidth
Tuukka Korhonen, Konrad Majewski, Wojciech Nadara +2
We present a data structure that for a dynamic graph that is updated by edge insertions and deletions, maintains a tree decomposition of of width at most under the p…
Simpler and faster algorithms for detours in planar digraphs
Meike Hatzel, Konrad Majewski, Michał Pilipczuk +1
In the directed detour problem one is given a digraph and a pair of vertices and~, and the task is to decide whether there is a directed simple path from to in $…
Flipper games for monadically stable graph classes
Jakub Gajarský, Nikolas Mählmann, Rose McCarty +6
A class of graphs is monadically stable if for any unary expansion of , one cannot interpret, in first-order logic, arbitrarily l…