Tuesday, 13:45 - 14:10 h, Room: H 3013


Kenjiro Takazawa
Covering cuts in bridgeless cubic graphs

Coauthors: Sylvia Boyd, Satoru Iwata


In this talk we are interested in algorithms for finding 2-factors that cover certain prescribed edge-cuts in bridgeless cubic graphs. 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 O(n3) 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 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 O(n3). We then improve this time complexity to O(n2 log4 n) by relaxing the condition of the initial 2-factor and elaborating the subsequent processes.


Talk 2 of the invited session Tue.2.H 3013
"Matching and related problems" [...]
Cluster 2
"Combinatorial optimization" [...]


  Payday Loans In Virginia. In this section we give only a brief summary recommendation for admission of Levitra Sale. Full information can be found in the instructions for receiving medications with vardenafil.