Boyd, Sylvia; Iwata, Satoru; Takazawa, Kenjiro Finding 2-factors closer to TSP tours in cubic graphs. (English) Zbl 1272.05190 SIAM J. Discrete Math. 27, No. 2, 918-939 (2013). Summary: In this paper we are interested in algorithms for finding 2-factors that cover certain prescribed edge-cuts in bridgeless cubic graphs. Since a Hamilton cycle is a 2-factor covering all edge-cuts, imposing the constraint of covering those edge-cuts makes the obtained 2-factor closer to a Hamilton cycle. We present an algorithm for finding a minimum-weight 2-factor covering all the 3-edge cuts in weighted bridgeless cubic graphs, together with a polyhedral description of such 2-factors and that of perfect matchings intersecting all the 3-edge cuts in exactly one edge. We further give an algorithm for finding a 2-factor covering all the 3- and 4-edge cuts in bridgeless cubic graphs. Both of these algorithms run in \({\text O}(n^{3})\) time, where \(n\) is the number of vertices. As an application of the latter algorithm, we design a 6/5-approximation algorithm for finding a minimum 2-edge-connected spanning subgraph in 3-edge-connected cubic graphs, which improves upon the previous best ratio of 5/4. The algorithm begins with finding a 2-factor covering all 3- and 4-edge cuts, which is the bottleneck in terms of complexity, and thus it has running time \({\text O}(n^{3})\). We then improve this time complexity to \({\text O}(n^{2} \log^{4}n)\) by relaxing the condition of the initial 2-factor and elaborating on the subsequent processes. Cited in 17 Documents MSC: 05C85 Graph algorithms (graph-theoretic aspects) 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) Keywords:bridgeless cubic graphs; minimum-weight 2-factor covering 3-edge cuts; polyhedral description of 2-factors covering 3-edge cuts; 2-factor covering 3- and 4-edge cuts; minimum 2-edge-connected spanning subgraphs PDFBibTeX XMLCite \textit{S. Boyd} et al., SIAM J. Discrete Math. 27, No. 2, 918--939 (2013; Zbl 1272.05190) Full Text: DOI Link