Since 2014
Constrained Edge-Splitting Problems
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Constrained Edge-Splitting Problems
|
|
| Creator |
Jordán, Tibor
|
|
| Description |
Splitting off two edges su, sv in a graph G means deleting su, sv andadding a new edge uv. Let G = (V +s,E) be k-edge-connected in V(k >= 2) and let d(s) be even. Lov´asz proved that the edges incident to scan be split off in pairs in such a way that the resulting graph on vertexset V is k-edge-connected. In this paper we investigate the existence ofsuch complete splitting sequences when the set of split edges has to meetadditional requirements. We prove structural properties of the set of thosepairs u, v of neighbours of s for which splitting off su, sv destroys k-edge-connectivity. This leads to a new method for solving problems of this type.By applying this method we obtain a short proof for a recent result ofNagamochi and Eades on planarity-preserving complete splitting sequences and prove the following new results: let G and H be two graphs on the same set V + s of vertices and suppose that their sets of edges incident to s coincide. Let G (H) be k-edge-connected (l-edge-connected, respectively) in V and let d(s) be even. Then there exists a pair su, sv which can be split off in both graphs preserving k-edge-connectivity (l-edge-connectivity, resp.) in V , provided d(s) >= 6. If k and l are both even then such a pair always exists. Using these edge-splitting results and the polymatroid intersection theorem we give a polynomial algorithm for the problem of simultaneously augmenting the edge-connectivity of two graphs by adding a (common) set of new edges of (almost) minimum size.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
1999-12-07
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/20106
10.7146/brics.v6i37.20106 |
|
| Source |
BRICS Report Series; No 37 (1999): RS-37 Constrained Edge-Splitting Problems
BRICS Report Series; No 37 (1999): RS-37 Constrained Edge-Splitting Problems 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/20106/17725
|
|
| Rights |
Copyright (c) 2015 BRICS Report Series
|
|