Approximate Edge Splitting

Michel X. Goemans · SIAM Journal on Discrete Mathematics · 2001

We show that, in any undirected graph, splitting-off can be performed while preserving all cuts of value at most 4/3 times the minimum value, and this is the best possible. This generalizes a classical splitting-off result of Lovász.

Read the paper · More papers on PaperTik