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 together with their incident edges. After each arrival, the algorithm must maintain a maximum-cardinality matching while minimizing the total num...
Júlia Baligács, B. Bosek, Paweł Putra et al.· 0 citations
A simple recursive algorithm is presented that computes, for every temporal clique on $n$ vertices, a temporal $3-spanner of size $n^{1+2/\sqrt{\ln n}}=n^{1+o(1)}$, thereby improving the previous best upper bound of $\widetilde{\mathcal{O}}(n^{3/2})$.
Júlia Baligács, Davide Bilò, Václav Blažej et al.· 0 citations
This paper presents an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model and gives a 1.5-competitive algorithm and provide a matching lower bound.
Júlia Baligács, B. Bosek, Y. Disser et al.· Embedded Systems and Applica...· 1 citation
It is proved that the competitive ratio of the online graph exploration problem is at least 4, improving on the previously best known lower bound of 10/3.
This work focuses on cycles, a simple graph class which nevertheless captures a key difficulty of online exploration, and develops a randomized algorithm for online exploration of cycles, giving the first provable advantage of randomization in online graph exploration.
Júlia Baligács, Jan Hkazla, Lena Volk· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
