|
Published in:
A new approach to undirected splitting-off is presented in this paper.
We study the behaviour of splitting-off algorithms when applied to the
problem of covering a symmetric skew-supermodular set function by a
graph. This hard problem is a natural generalization of many solved
connectivity augmentation problems, such as local edge-connectivity
augmentation of graphs, global arc-connectivity augmentation of mixed
graphs with undirected edges, or the node-to-area connectivity
augmentation problem in graphs. Using a simple lemma we characterize
the situation when a splitting-off algorithm can be stuck. This
characterization enables us to give very simple proofs for the
classical results mentioned above. Finally we apply our observations
in generalizations of the above problems: we consider three
connectivity augmentation problems in hypergraphs with hyperedges of
minimum total size without increasing the rank. The first is the
local edge-connectivity augmentation of undirected hypergraphs.
The second is global arc-connectivity augmentation of mixed
hypergraphs with undirected hyperedges.
The third is a hypergraphic generalization of the node-to-area
connectivity augmentation problem. We show that a greedy approach
works in (almost) all of these cases.
Previous version can be found here.
Bibtex entry:
| AUTHOR | = | {Bern{\'a}th, Attila and Kir{\'a}ly, Tam{\'a}s}, |
| TITLE | = | {A new approach to splitting-off}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2008}, |
| NUMBER | = | {TR-2008-02} |