Covering symmetric supermodular functions with graph edges: a short proof of a theorem of Benczúr and Frank

DOI10.1016/j.ipl.2017.08.003zbMath1420.05141OpenAlexW2750675246MaRDI QIDQ2404617

Attila Bernáth

Publication date: 19 September 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2017.08.003

zbMATH Keywords

polynomial algorithmgraph algorithmsedge-connectivity augmentationcrossing supermodular function

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Edge-connectivity augmentation problems
• Augmenting hypergraphs by edges of size two
• Covering symmetric supermodular functions by graphs
• A New Approach to Splitting-Off
• Augmenting Graphs to Meet Edge-Connectivity Requirements

This page was built for publication: Covering symmetric supermodular functions with graph edges: a short proof of a theorem of Benczúr and Frank