News

2021年07月22日

Prof. KAWARABAYASHI Ken-ichi won The 2021 Fulkerson Prize

Award

The Fulkerson Prize

Name

KAWARABAYASHI Ken-ichi (NII)
Mikkel Thorup(University of Copenhagen)

Title

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. "

Organization

Mathematical Optimization Society
American Mathematical Society

Date

July 22, 2021

Link

• Fulkerson Prize awarded for work in discrete mathematics - AMS :: News from the AMS
• AMS :: Delbert Ray Fulkerson Prize (AMS-MOS)
• Deterministic Edge Connectivity in Near-Linear Time
  (Journal of the ACM Vol.66 No.1, 2018)
• Researcher Profiles: KAWARABAYASHI Ken-ichi - Principles of Informatics Research Division Professor
• Large Graphs:Theory and Algorithms
• Kawarabayashi Large Graph Project

• ツイート