Leírás
Applied Disrete Math seminar
Abstract: In this work, we present the first linear time deterministic
algorithm computing the 4-edge-connected components of an undirected
graph. Linear time algorithms for 3-edge-connectivity and
4-vertex-connectivity were already known.
In this paper first, we show how to reduce the problem of determining
4-edge-connected components to the problem of determining 4-edge-connected
components in 3-edge-connected graph. Then we show a linear time, randomized
algorithm for listing all 3-edge-cuts in 3-edge-connected graphs. After that,
we show how to remove the dependency on the randomness in the algorithm,
producing a linear time, deterministic algorithm listing all 3-edge-cuts in
3-edge-connected graphs. Finally we construct a tree of 3-edge-cuts in a
3-connected graph, given the list of all its 3-edge cuts. This tree is then
used to determine the 4-edge-connected components of the graph.