User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Approximate edge splitting

Primary tabs

download
  • Open access
  • PDF
  • 71.49 K
Goemans, Michel X.

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 best possible. This generalizes a classical splitting-off result of Lovasz.

Document type Document de travail (Working Paper)
Access type Accès libre
Publication date 1999
Collection CORE Discussion Papers - 1999/37
Affiliation UCL - CORE - Center for Operations Research and Econometrics
Links
Bibliographic reference Goemans, Michel X.. Approximate edge splitting. CORE Discussion Papers ; 1999/37 (1999)
Permanent URL http://hdl.handle.net/2078.1/4049