Splitting off edges between two subsets preserving the edge-connectivity of the graph.
type: Item
instance of: scholarly article
title: Splitting off edges between two subsets preserving the edge-connectivity of the graph.
zbMATH Open document ID: 1039.05037
DOI: 10.1016/S0012-365X(03)00291-7
author: Tibor Jordán
author: Jørgen Bang-Jensen
published in: Discrete Mathematics
publication date: 2004-02-14T00:00:00Z
review text: Splitting off a pair of edges \(su\), \(sv\) in a graph means replacing these two edges by a new edge \(uv\). Let \(G=(V+s,E)\) be a graph which is \(k\)-edge connected in \(V\) (i.e., there are at least \(k\) edge-disjoint paths between every pair of vertices of \(V\)) and suppose that the degree of \(s\) is even. \textit{L. Lovász} [Combinatorial problems and exercises (North-Holland, Amsterdam) (1993; Zbl 0785.05001)] proved that if \(k\geq 2\) then the edges incident with \(s\) can be split off in pairs preserving the \(k\)-edge connectivity in \(V\). In the paper under review, the authors study the following \((R,Q)\)-split completion problem: given a graph \(G=(V+s,E)\) which is \(k\)-edge connected in \(V\), disjoint subsets \(R\), \(Q\) of \(V\) and an integer \(k\geq2\), find a minimum cardinality set \(F\) of new edges incident with \(s\) such that in the new graph \(G+F\), all edges incident with \(s\) can be split off preserving the \(k\)-edge connectivity in \(V\) where every edge from \(s\) to \(R\) in \(G\) is split off with an edge from \(s\) to \(Q\). First, the problem of finding the longest possible sequence of ``admissible \((R,Q)\)-splits'' is solved. The length of such a sequence is characterized by certain ``obstacles'', i.e., substructures of \(G\) which preclude the existence of long admissible \((R,Q)\)-splitting sequences. An algorithm to find a longest sequence is given. Then this algorithm is used iteratively to solve the \((R,Q)\)-split completion problem when \(k\) is even. For odd \(k\), an almost optimal (at most two edges more than the optimum) solution is found.
reviewed by: Clemens Heuberger
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 2041892
zbMATH Keywords: edge-connectivity augmentation
zbMATH Keywords: split completion problem
zbMATH Keywords: partition constrained augmentation
MaRDI profile type: Publication
cites work: Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
cites work: Edge-Connectivity Augmentation with Partition Constraints
cites work: Edge-Connectivity Augmentation Preserving Simplicity
cites work: Splitting Off Edges within a Specified Subset Preserving the Edge-Connectivity of the Graph
cites work: The minimum augmentation of any graph to aK-edge-connected graph
cites work: Q3828033
cites work: Augmenting Graphs to Meet Edge-Connectivity Requirements
cites work: Q4845372
cites work: Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
cites work: Q3880849
cites work: A Reduction Method for Edge-Connectivity in Graphs
cites work: Konstruktion aller n-fach kantenzusammenhaengenden Digraphen
cites work: Q3840350
full work available at URL: s0012-365x(03)00291-7
OpenAlex ID: W2058149194
description: scientific article; zbMATH DE number 2041892