Splitting off edges between two subsets preserving the edge-connectivity of the graph.

DOI10.1016/S0012-365X(03)00291-7MaRDI QIDQ1422410zbMATH OpenOpenAlexFDO

Authors Tibor Jordán, Jørgen Bang-Jensen

Publication date 14 February 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(03)00291-7

zbMATH Keywords

edge-connectivity augmentation partition constrained augmentation split completion problem

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85)

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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Splitting off edges between two subsets preserving the edge-connectivity of the graph.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1422410)