MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Cross-Paradigm Graph Algorithms

Danupon Nanongkai
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Tuesday, 2 July 2024
13:00
60 Minutes
E1 4
024
Saarbrücken

Abstract

A goal of the theory of graph algorithms is algorithmic

techniques that enable computing devices to process graph data with
little resources (time, space, communication overhead, etc.). This led
to extensive studies of graph algorithms in various models of
computation (sequential algorithms, distributed algorithms, streaming
algorithms, etc.) by many sub-communities. "Cross-paradigm graph
algorithms" is an effort to attack the same problem in many models of
computation simultaneously, intending to generate new insights that may
not emerge from the isolated viewpoint of a single model and to
ultimately develop techniques that can be used to solve graph problems
near-optimally across many models of computation.

In this talk, I will discuss some recent advances in graph algorithmic
techniques for basic graph problems (e.g. minimum cut, shortest path,
and maximum flow) in connection to this research program, especially
some insights that led to cross-paradigm algorithms and to answering
notorious open questions.

Contact

Nidhi Rathi
+49 681 9325 1134
--email hidden

Virtual Meeting Details

Zoom
897 027 2575
passcode not visible
logged in users only

Nidhi Rathi, 06/12/2024 16:29 -- Created document.