3 citations · 3 across the 12 of their papers we have counts for
15 papers
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 -…
Geometric opinion exchange polarizes in every dimension
Abdou Majeed Alidou, Júlia Baligács, Jan Hązła
A recent line of work studies models of opinion exchange where agent opinions about topics are tracked simultaneously. The opinions are represented as vectors on the unit $(d-1…
Symmetry classes of Hamiltonian cycles
Julia Baligacs, Sofia Brenner, Annette Lutz +1
We initiate the study of Hamiltonian cycles up to symmetries of the underlying graph. Our focus lies on the extremal case of Hamiltonian-transitive graphs, i.e., Hamiltonian graphs…
The metric Menger problem
Júlia Baligács, Joseph MacManus
We study a generalization of the well-known disjoint paths problem which we call the metric Menger problem, denoted MM(r,k), where one is given two subsets of a graph and must deci…
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 (…
Inevitability of Polarization in Geometric Opinion Exchange
Abdou Majeed Alidou, Júlia Baligács, Max Hahn-Klimroth +3
Polarization and unexpected correlations between opinions on diverse topics (including in politics, culture and consumer choices) are an object of sustained attention. However, num…
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.…