3 citations · 3 across the 12 of their papers we have counts for
7 papers · 1 filter
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…
A lower bound of 4 for online graph exploration
Julia Baligacs
In the online graph exploration problem, a single agent needs to visit every vertex of an initially unknown graph, which is learned over time in an online fashion, and return to it…
Randomization Helps in Online Graph Exploration: Breaking the Deterministic Lower Bound on Cycles
Júlia Baligács, Jan Hązła, Lena Volk
In online graph exploration, introduced by Kalyanasundaram and Pruhs (1994), an agent must visit all vertices of an initially unknown weighted graph and return to its starting posi…
A coarse block-cut tree theorem
Júlia Baligács, Václav Blažej, Jadwiga Czyżewska +2
We prove a coarse analogue of the classic fact that every graph can be decomposed along its cut-vertices into -connected components. Precisely, we prove that for every graph …
Temporal Cliques Admit Linear Spanners
Julia Baligacs
A temporal graph is a graph in which every edge carries a non-empty set of time labels, and it is temporally connected if for every two vertices and , there exists a -…