7 papers · 1 filter
Tight Competitive Bounds for Online Matching on Forests
Bartłomiej Bosek, Grzegorz Gutowski, Paweł Putra +1
We study the online matching problem, its fractional relaxation, and the fractional online vertex cover problem on forests whose edges arrive one at a time in an arbitrary order. M…
Partially Dynamic Algorithms for Single-Source Temporal Paths
Davide Bilò, Bartłomiej Bosek, Jadwiga Czyżewska +3
We present efficient partially dynamic algorithms for maintaining earliest arrival times from a fixed source in temporal digraphs with vertices. For the incremental scenario wh…
Almost Linear 3-Spanners of Temporal Cliques
Julia Baligacs, Davide Bilò, Václav Blažej +2
Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in…
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…
A tight lower bound for malicious online bipartite matching with limited recourse budget
Julia Baligacs, Bartłomiej Bosek, Paweł Putra +2
We study one-sided online bipartite matching with recourse. In this setting, one side of a bipartite graph is known in advance, while vertices on the other side arrive online toget…
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…
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…