2 czerwca 2026 11:00
[Seminarium ZOK] Shinwoo An: Near-Linear Time Approximation Scheme for Weighted Diameter in Planar Digraphs
Computing the diameter of a graph is a fundamental problem
in algorithmic graph theory. For weighted planar graphs, both directed
and undirected, the best known exact algorithms require
$\tilde{O}(n^{5/3})$ time. While $(1+\eps)$-approximations in
near-linear time have been known for undirected planar graphs for over
a decade, the directed setting has remained a major open problem due
to the challenges posed by distance asymmetry.
In this talk, I will present the first deterministic near-linear time
algorithm that computes a $(1+\eps)$-approximation for the diameter of
edge-weighted directed planar graphs. Our main technical contribution
is a new machinery that overcomes the asymmetry inherent in directed
planar graph separators. This new machinery provides a robust
framework for handling the distance asymmetry that we anticipate will
be applicable both to closely related problems and to other classes of
directed graphs admitting similar separator properties.
Joint work with Avi Kadria, Wolfgang Mulzer, and Liam Roditty.