Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem

Mingyu Xiao, Leizhen Cai, Andrew C. Yao

For an edge-weighted connected undirected graph, the minimum $k$-way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into $k$ con…