A unifying approach to splitting-off
A symmetric skrew-supermodular set function \(p\) is covered by a hypergraph \(H\) if each subset \(X\) of the vertex set \(V\) is introduced by at least \(p(X)\) hyperedges. In case of a degree specification \(m(v)\) for \(v\) from \(V\), the question is whether a hypergraph \(G\) covering \(p\) exists such that the degree of each vertex \(v\) in \(G\) equals \(m(v)\). If there is a solution then there is also a solution to the minimum version in which the sum of the sizes of the hyperedges is minimized because of \(p\) being skrew-supermodular. The problem with specified degrees generalizes many connectivity augmentation problems. The minimum version and therefore the degree-specified version are \(NP\)-complete but special cases are polynomially solvable. The idea bases on a technique called splitting-off: first find a set of graph edges covering \(p\) of minimum cardinality and incident to a new vertex \(s\), then split off pairs of to \(s\) incident edges.
- A New Approach to Splitting-Off
- Covering symmetric supermodular functions by uniform hypergraphs
- Covering skew-supermodular functions by hypergraphs of minimum total size
- Covering symmetric supermodular functions by graphs
- Splitting Off Edges within a Specified Subset Preserving the Edge-Connectivity of the Graph
- A New Approach to Splitting-Off
- A Reduction Method for Edge-Connectivity in Graphs
- Approximating connectivity augmentation problems
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Covering symmetric semi-monotone functions
- Covering symmetric supermodular functions by graphs
- Hypergraph connectivity augmentation
- Local edge-connectivity augmentation in hypergraphs is NP-complete
- Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs
- On a theorem of Mader
- Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
- Covering skew-supermodular functions by hypergraphs of minimum total size
- The transition to unigroups
- Minimal edge-coverings of pairs of sets
- Approximation algorithms for connectivity augmentation problems
- A strategic approach to multiple estate division problems
- The generalized terminal backup problem
- A New Approach to Splitting-Off
- Covering symmetric supermodular functions by uniform hypergraphs
- Approximation algorithms for node and element connectivity augmentation problems
- Splitting-off in hypergraphs
- Splitting-off in hypergraphs
This page was built for publication: A unifying approach to splitting-off
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2448935)
