Prof. KAWARABAYASHI Ken-ichi won The 2021 Fulkerson Prize
The Fulkerson Prize
KAWARABAYASHI Ken-ichi (NII)
Mikkel Thorup(University of Copenhagen)
Deterministic Edge Connectivity in Near-Linear Times
The citation for the award
"Determining the edge connectivity of a graph is one of the most
fundamental graph problems. Kawarabayashi and Thorup's work does not just
improve the running time of the algorithm, impressive as that is.
Its main contributions are conceptual:the paper introduces powerful and impactful
new ideas that will have a long-lasting influence on the field.
The most powerful of these ideas is a fast deterministic sparsification
that essentially preserves all the non-trivial minimum cuts of the graph. "
Mathematical Optimization Society
American Mathematical Society