Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 30, 2023, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Julian Portmann
The arboricity arb(G) of a graph G is the minimum number of forests needed to cover all its edges. Recently, Eden, Mossel, and Ron [SODA'22] gave a randomized sublinear time algorithm for computing a O(log²n) approximation of arboricity with (near-optimal) Õ(n / arb(G)) queries, where a query is reading the degree or the i-th neighbor of a given vertex.
In this talk, I will present a simple randomized algorithm that improves this approximation to O(log n) with the same number of queries. This is joint work with Mohsen Ghaffari.
Automatic MiSe System Software Version 1.4803M | admin login