Showing 2024Show all
3 papers · 1 filter
cs.DS2024
Dynamic Parameterized Feedback Problems in Tournaments
Anna Zych-Pawlewicz, Marek Żochowski
In this paper we present the first dynamic algorithms for the problem of Feedback Arc Set in Tournaments (FAST) and the problem of Feedback Vertex Set in Tournaments (FVST). Our al…
cs.DS2024
A -Approximation for Tricolored Non-crossing Euclidean TSP
Júlia Baligács, Yann Disser, Andreas Emil Feldmann +1
In the Tricolored Euclidean Traveling Salesperson problem, we are given~ sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (…
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…