Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Online and Incremental Fractional Vertex Cover on Trees
Júlia Baligács, Bartłomiej Bosek, Yann Disser +5
In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori…
cs.DS2026
Dynamic domination and independence in sparse graphs
BartÅomiej Bosek, Wojciech Nadara, MichaÅ Pilipczuk +1
Let be a class of graphs of bounded expansion and be fixed. We give a dynamic data structure that for a given dynamic graph , updated by edge i…
cs.DS2026
Dynamic data structures for twin-ordered matrices
BartÅomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis +4
We present a dynamic data structure for representing binary matrices that are -twin-ordered, for a~fixed parameter . Our structure supports cell queries and singl…