F. Grandoni

activity

20072024

most citedOn Pairwise Spanners

21 citations · 89 across the 29 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

cs.DS2020

Online Edge Coloring Algorithms via the Nibble Method

Sayan Bhattacharya, Fabrizio Grandoni, David Wajc

Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online $(1 + o (1)) Δ$ -edge-coloring algorithm exists for $n$ -node graphs of maximum degree $Δ=ω(\log n)…

cs.DS2020

Improved Approximation Algorithms for Stochastic-Matching Problems

Marek Adamczyk, Brian Brubach, Fabrizio Grandoni +3

We consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. In this problem, we are given an undirected graph. Each edge i…

cs.DS2020★ 1 cited

All-Pairs LCA in DAGs: Breaking through the $O (n^{2.5})$ barrier

Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Łukasiewicz +2

Let $G = (V, E)$ be an $n$ -vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices $u$ and $v$ is a common ancestor $w$ of $u$ and $v$ such that no descend…

Online Edge Coloring Algorithms via the Nibble Method

Improved Approximation Algorithms for Stochastic-Matching Problems

All-Pairs LCA in DAGs: Breaking through the O(n2.5) barrier

All-Pairs LCA in DAGs: Breaking through the $O (n^{2.5})$ barrier