Covering symmetric supermodular functions by graphs

DOI10.1007/s101070050034zbMath0931.05068OpenAlexW2022577990MaRDI QIDQ1300054

András Frank, András A. Benczúr

Publication date: 23 November 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s101070050034

zbMATH Keywords

hypergraph connectivity augmentationsupermodular set-function

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs, Covering symmetric supermodular functions by uniform hypergraphs, Covering symmetric supermodular functions with graph edges: a short proof of a theorem of Benczúr and Frank, The Generalized Terminal Backup Problem, A New Approach to Splitting-Off, Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph, Edge-Connectivity Augmentations of Graphs and Hypergraphs, A unifying approach to splitting-off, Augmenting edge-connectivity between vertex subsets, Tight approximation algorithm for connectivity augmentation problems, Covering symmetric semi-monotone functions, Augmenting the Edge‐Connectivity of a Hypergraph by Adding a Multipartite Graph, Local edge-connectivity augmentation in hypergraphs is NP-complete, The \((2, k)\)-connectivity augmentation problem: algorithmic aspects, Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs, Testing the supermodular-cut condition, Approximation algorithms for connectivity augmentation problems