:::

[TIGP-AIoT Seminar] Distributed Graph Algorithms and Expander Routing


  • 講者 : 黃上恩 教授
  • 日期 : 2025/05/09 (Fri.) 14:00~16:00
  • 地點 : 資創中心122演講廳
  • 邀請人 : TIGP-AIoT Program
Abstract
Graphs are powerful mathematical objects that provide the right level of abstraction for modeling and solving many real-world problems. In vertex-centric distributed computing, computation nodes communicate via network links, which can naturally be represented as vertices and edges of a graph. Algorithms can then be designed to run on each computation node, enabling all nodes to collaboratively solve a given problem.

In this talk, I will introduce a line of research in theoretical computer science focused on solving graph problems in distributed networks. A classical example is the packet routing problem, where all computation nodes simultaneously route packets to their desired destinations while avoiding congestion. In particular, I will present an algorithm that solves the packet routing problem on expander graphs — networks that are highly connected yet sufficiently sparse.

This talk is based on joint work with Hsin-Hao Su and Yi-Jun Chang.