Approximates Edge Splitting.

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

MoreLess

Year of publication:	1999
Authors:	Goemans, M.X.
Institutions:	Center for Operations Research and Econometrics (CORE), École des Sciences Économiques de Louvain
Subject:	MATHEMATICS

More details

Series:	Papers.
Type of publication:	Book / Working Paper
Notes:	5 pages
Classification:	C60 - Mathematical Methods and Programming. General
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005634031