3 papers
cs.DS2024
Parameterized dynamic data structure for Split Completion
Konrad Majewski, Michał Pilipczuk, Anna Zych-Pawlewicz
We design a randomized data structure that, for a fully dynamic graph updated by edge insertions and deletions and integers fixed upon initialization, maintains the answ…
cs.DS2023
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…
cs.DS2020
The Asymmetric Travelling Salesman Problem in Sparse Digraphs
Łukasz Kowalik, Konrad Majewski
Asymmetric Travelling Salesman Problem (ATSP) and its special case Directed Hamiltonicity are among the most fundamental problems in computer science. The dynamic programming algor…