A linear-time algorithm for finding an edge-partition with max-min ratio at most two
ChuAn-Chiang, WuBang Ye, ChaoKun-Mao · Discrete Applied Mathematics · 2013
Given a positive integer k and an undirected edge-weighted connected simple graph G with at least k edges of positive weight, we wish to partition the graph into k edge-disjoint connected component...