Article ID Journal Published Year Pages File Type
428471 Information Processing Letters 2016 4 Pages PDF
Abstract

The minimum 2-edge connected spanning subgraph problem in 3-edge connected cubic bipartite graphs is addressed. For the nonbipartite case, the previous best approximation ratio has been 6/5. We exhibit the advantage of bipartiteness to attain an improved ratio 7/6.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
Authors
,