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" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.