NETWORKS day
On Monday, June 16, the next and final NETWORKS Day will take place at the University Museum Utrecht. Because of this special occasion, the setup will be slightly different than usual. You are warmly invited to join this final edition of the Networks day.
Throughout the NETWORKS day, presentations will be delivered by Ferenc Bencs (CWI), Akrati Saxena (Leiden University) and Yasamin Nazari (Vrije Universiteit Amsterdam). The program begins at 13:00 AM and concludes with a buffet at the restaurant of "De Oude Hortus" in Utrecht.
Programme
13.00 - 13.30 | Coffee and welcome |
13.30 - 14.20 | Akrati Saxena (Leiden University) |
14.20 - 14.50 | Break |
14.50 - 15.40 | Yasamin Nazari (Vrije Universiteit Amsterdam) |
15.40 - 16.10 | Break |
16.10 - 17.00 | Ferenc Bencs (CWI) |
17.00 - 20.00 | Drinks and dinner |
Abstracts
Akrati Saxena
Algorithmic Fairness in Social Network Analysis: FairSNA
Yasamin Nazari
Graph Distance Structures and their Algorithmic Applications
In recent years there has been a growing interest in studying graph theoretical structures used for designing efficient algorithms in various computational models, such as dynamic, parallel and distributed models.
In this talk, I focus on distance structures which are objects that preserve approximate distances in a graph, but tradeoff this approximation factor with space, query time, or the number of hops on the approximate shortest paths. I will also discuss how these structures can be utilized for faster shortest path computation in dynamic and parallel models.
Ferenc Bencs
Two tales of sink-free orientationsIn this talk we will investigate the (number of) sink-free orientations in a graph. It turns out this number is actually #P hard to compute for general graphs. Using the fact that any orientation can be checked whether it's sink-free using local information, quite efficient randomized algorithms were developed to approximate the number sink-free orientations. Very recently the first deterministic algorithm was introduced by Anand et. al. In this talk, we will further exploit its close relation to the Lovász Local lemma and improve on the best deterministic approximation algorithm for this number if the minimum degree of the graph is at least 3.As a different application, we will determine the rate of the reliability probability of random regular graphs, which is the probability that after a 1/2-percolation, the graph remains connected.The results are based on joint works with Márton Borbényi, Péter Csikvári and Guus Regts.