Authors
Citation
Mx. Goemans, Approximate edge splitting, SIAM J DISC, 14(1), 2001, pp. 138-141
Citations number
7
Categorie Soggetti
Engineering Mathematics
Journal title
SIAM JOURNAL ON DISCRETE MATHEMATICS
ISSN journal
08954801
→ ACNP
Volume
14
Issue
1
Year of publication
2001
Pages
138 - 141
Database
ISI
SICI code
0895-4801(2001)14:1<138:AES>2.0.ZU;2-V
Abstract
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
Lovasz.