Approximate edge splitting

DOI10.1137/S0895480199358023MaRDI QIDQ2706195zbMATH OpenFDO

Authors Michel X. Goemans

Publication date 19 March 2001

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480199358023

zbMATH Keywords

edge splittinggraph connectivity

Mathematics Subject Classification ID

Connectivity (05C40)

Review text

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.

Recommendations

• Splitting off edges between two subsets preserving the edge-connectivity of the graph.
• Constrained Edge-Splitting Problems
• scientific article; zbMATH DE number 1256720
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
• Splitting Off Edges within a Specified Subset Preserving the Edge-Connectivity of the Graph

Cited in

(5)

• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• On splitting off operation for graphs and its applications
• Fission of halving edges graphs
• Splitting-off in hypergraphs
• Splitting-off in hypergraphs

This page was built for publication: Approximate edge splitting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2706195)