Dynamic graph algorithms: What they are and why they are needed?
Date
Monday, November 12, 2018 16:00 - 17:00
Speaker
Monika Henzinger (University of Vienna)
Location
Raiffeisen Lecture Hall
Series
Colloquium
Tags
Institute Colloquium
Contact
Graphs are used in many application domains to model entities and their relationships, such as social networks, the world-wide web, road maps, and communication networks. In a social network, for example, the entities are the users and their relationships are induced by their friendships in the social network. As a recent study showed, graphs modeling over a billion pair-wise relationships are ubiquitous. Additionally, many such graphs are not static, but are subject to a variety of changes. This leads to question how quickly information about a graph, for example which entities form clusters, can be updated when a change occurs. We will survey the state-of-the art of this research area on dynamic graph algorithms.