𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Finding 2-edge connected spanning subgraphs

✍ Scribed by Woonghee Tim Huh

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
185 KB
Volume
32
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

This paper studies the NP-hard problem of ΓΏnding a minimum size 2-edge connected spanning subgraph (2-ECSS). An algorithm is given that on an r-edge connected input graph G =(V; E) ΓΏnds a 2-ECSS of size at most |V |+(|E|-|V |)=(r -1). For r-regular, r-edge connected input graphs for r = 3, 4, 5 and 6, this gives approximation guarantees of 5 4 ; 4 3 ; 11 8 and 7 5 , respectively.

πŸ“œ SIMILAR VOLUMES

Spanning even subgraphs of 3-edge-connec
Spanning even subgraphs of 3-edge-connected graphs
✍ Bill Jackson; Kiyoshi Yoshimoto πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 344 KB

## Abstract By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connec

2-Connected Spanning Subgraphs of Planar
2-Connected Spanning Subgraphs of Planar 3-Connected Graphs
✍ D.W. Barnette πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 278 KB

We prove that every planar 3-connected graph has a 2-connected spanning subgraph of maximum valence 15 . We give an example of a planar 3 -connected graph with no spanning 2-connected subgraph of maximum valence five. i) 1994 Academic Press, Inc.

On finding spanning eulerian subgraphs
On finding spanning eulerian subgraphs
✍ M. B. Richey; R. Gary Parker; R. L. Rardin πŸ“‚ Article πŸ“… 1985 πŸ› John Wiley and Sons 🌐 English βš– 649 KB