3 citations · 3 across the 12 of their papers we have counts for
9 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 -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 (…
Exploration of graphs with excluded minors
Julia Baligacs, Yann Disser, Irene Heinrich +1
We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and…
An Improved Algorithm for Open Online Dial-a-Ride
Julia Baligacs, Yann Disser, Nils Mosis +1
We consider the open online dial-a-ride problem, where transportation requests appear online in a metric space and need to be served by a single server. The objective is to minimiz…
Tight analysis of the lazy algorithm for open online dial-a-ride
Julia Baligacs, Yann Disser, Farehe Soheil +1
In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time.…