Mikkel Thorup receives a Fulkerson Prize
Professors Thorup and Kawarabayashi have won an esteemed Fulkerson Prize for their paper “Deterministic Edge Connectivity in Near-Linear Time”.
The 2021 Fulkerson Prize recognizes outstanding papers in discrete mathematics and is awarded jointly by the American Mathematical Society (AMS) and the Mathematical Optimization Society (MOS) only once every third year. The award is given for mathematical excellence in discrete mathematics, including graph theory, networks, mathematical programming, applied combinatorics, applications of discrete mathematics to computer science, and related subjects. Ken-Ichi Kawarabayashi and Mikkel Thorup have received one of three prizes given this year for their paper “Deterministic Edge Connectivity in Near-Linear Time,” which appeared in 2018 in Journal of the Association for Computing Machinery, vol. 66, no. 1.
“Determining the edge connectivity of a graph is one of the most fundamental graph problems,” the committee wrote in the citation. “Karger’s 1996 breakthrough gave a randomized algorithm that runs in near-linear time. It took a long time, and a lot of new ideas, before Kawarabayashi and Thorup could find a deterministic algorithm. This 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.”