Approximate edge splitting (Q2706195)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Approximate edge splitting |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Approximate edge splitting |
scientific article |
Statements
19 March 2001
0 references
graph connectivity
0 references
edge splitting
0 references
Approximate edge splitting (English)
0 references
Let \(e=(s,u)\) and \(f=(s,v)\) be two edges in an undirected graph \(G.\) Then splitting off \(e\) and \(f\) means deleting them from \(G\) and adding the edge \((u,v).\) The author shows that in any \(G\) splitting-off can be performed so that all cuts of value \(4/3\) times the minimum value of a cut are preserved. Moreover, this result is the best possible.
0 references
