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 in graphs of degeneracy at most $d, one can maintain an ${cal O}(d^2)$-approximation of the minimum size of a (distance-$1) dominating set with amortized expected update time $d^{{\cal O}(1)}\cdot \log n$.
B. Bosek, Wojciech Nadara, Michał Pilipczuk et al.· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
