國立清華大學 數學系

Abstract:
Given a graph and a function on its vertices, how do we partition the vertices into clusters so that (1) vertices with similar function values are in the same cluster and (2) the induced subgraph on each cluster is connected as much as possible? Such a problem has applications in detecting the sources of air pollution, image segmentation, and so on. We will go through the theoretical background of this algorithm and demonstrate some of its applications.