An Upper Bound of 7n/6 for the Minimum Size 2EC on Cubic 3-Edge Connected Graphs

2017/06/06 by Legault, Philippe
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1706.01609

Abstract

In this paper, we study the minimum size 2-edge connected spanning subgraph problem (henceforth 2EC) and show that every 3-edge connected cubic graph G=(V, E), with n=|V| allows a 2EC solution for G of size at most 7n/6, which improves upon Boyd, Iwata and Takazawa's guarantee of 6n/5.

Related

• A New Approximation Algorithm for the Minimum 2-Edge-Connected Spanning Subgraph Problem
• On the minimum leaf number of cubic graphs
• A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
• A 17/12-Approximation Algorithm for 2-Vertex-Connected Spanning Subgraphs on Graphs with Minimum Degree At Least 3
• A 5/4-Approximation for Two-Edge Connectivity